#P6604. [2023山东第三轮省队集训]跳

    ID: 6453 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-线性 DP前后缀最值

[2023山东第三轮省队集训]跳

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;

第二行有 nn 个用空格分隔的非负整数 a1,…,ana_1,\ldots,a_n。

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

1≤n≤30001\le n\le3000。本站保证在修改前至少存在一条从第 11 格到第 nn 格的路径。

Output

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

Samples

4
1 1 1 0
0