问题文

Mixi公司的员工青木先生拥有一个由 $N$ 个元素组成的数列 $A$，一开始该数列的所有元素都是 $0$。

青木先生希望通过执行以下操作 $0$ 次或更多次，使得数列中的第 $i$ 个元素等于 $a_i$，其中 $1 \leq i \leq N$。

• 选择满足 $1 \leq k \leq N$ 和 $1 \leq l \leq N+1-k$ 的正整数 $k$ 和 $l$。随意选择长度为 $k$ 的非负整数序列 $(0 \leq )B_1 \leq B_2 \leq ... \leq B_k$，并将 $A_{l+i-1}$ 更新为 $A_{l+i-1} + B_i$，其中 $1 \leq i \leq k$。

每次操作可以使用不同的 $k, l, B$。请计算出青木先生需要进行的最少操作次数，以获得目标数列。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$
• 所有输入均为整数

输入

输入从标准输入读取。输入的格式如下所示。

$N$ $a_1$ $a_2$ $...$ $a_N$

输出

输出青木先生需要进行的最少操作次数。

输入样例 1

2
3 4

输出样例 1

1

如果选择 $k = 2, l = 1, B = \{3, 4\}$，则青木先生可以在一次操作中获得目标数列。

输入样例 2

2
4 3

输出样例 2

2

在第一次操作中，选择 $k = 2, l = 1, B = \{3, 3\}$，则 $A$ 变为 $\{3, 3\}$。

在第二次操作中，选择 $k = 1, l = 1, B = \{1\}$，则 $A$ 变为 $\{4, 3\}$。

因此，青木先生可以在两次操作中获得目标数列，并且无法在一次操作中获得目标数列，所以输出为 $2$。

输入样例 3

4
4 0 4 0

输出样例 3

2