Description

有n个格子，初始棋子在第1个格子，目标是让棋子到达第n个格子。

目前有一个数组a_i，当棋子位于第i个格子时，它可以跳到第i+1到i+a_i个格子（0≤a_i≤n-i）。

如果它还没到达第n个格子，但当前格子的a_i=0，那游戏就失败了。

这个问题太简单了，所以你想加强一下，将一部分a_i变成0，使得到达第n个格子的方法唯一。

Format

Input

第一行一个正整数n；

第二行n个用空格分割的正整数a_1,…,a_n。

保证a_i满足0≤a_i≤n-i。

n≤3000

Output

一行，一个整数，代表最少将多少个a_i变成0。

Samples

4
1 1 1 0

0