题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。

定义 $a$ 为“好”的，当且仅当存在 $b_1,b_2,\cdots,b_m$ 使得：

1. $b_i$ 为 $1 \sim n$ 的整数；
2. $a_i = \min\limits_{b_j \le i} \{i-b_j\}$。

注意：为了使得条件 $2$ 中的式子有意义，至少需要存在一个 $b_x=1$。

你可以进行若干次操作，每次操作选择 $x,y$，将 $a_x \gets y$，付出 $1$ 的代价。

你至少要付出多少代价，才能使 $a$ 变为“好”的？

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

一行一个整数，表示至少需要付出的代价。

样例

2
0 2

1

5
0 1 3 1 1

2

样例解释

• #1：修改为 $0,1$。
• #2：修改为 $0,1,2,0,1$。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^7$，$0 \le a_i < n$。

• Subtask #1（$1 \text{ pt}$）：$n=1$。
• Subtask #2（$19 \text{ pts}$）：$n \le 300$。
• Subtask #3（$29 \text{ pts}$）：$n \le 4 \times 10^3$。
• Subtask #4（$20 \text{ pts}$）：$n \le 2 \times 10^5$。
• Subtask #5（$31 \text{ pts}$）：无特殊限制。