AT_bcu30_2019_b.Interval Addition

ミクシィ公司的青木先生有一个由 $N$ 个元素组成的数列 $A$，初始时数列的所有元素均为 $0$。

青木先生可以重复进行以下操作 $0$ 次或多次，使得对于所有 $1 \leq i \leq N$，数列第 $i$ 个元素变为 $a_i$。

• 选择满足 $1 \leq k \leq N$ 和 $1 \leq l \leq N+1-k$ 的正整数 $k, l$。任意选择一个长度为 $k$ 的非负整数序列 $0 \leq B_1 \leq B_2 \leq \cdots \leq B_k$，然后对于 $1 \leq i \leq k$，令 $A_{l+i-1} := A_{l+i-1} + B_i$。

每次操作可以选择不同的 $k, l, B$。请你求出青木先生为了得到目标数列，所需的最少操作次数。

输入以如下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\cdots$ $a_N$

输出青木先生为了得到目标数列所需的最小操作次数。

限制条件

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

样例解释 1

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

样例解释 2

第一次操作选择 $k=2, l=1, B=\{3, 3\}$，此时 $A$ 变为 $\{3, 3\}$。第二次操作选择 $k=1, l=1, B=\{1\}$，此时 $A$ 变为 $\{4, 3\}$。因此青木先生可以通过 $2$ 次操作得到目标数列，且无法通过 $1$ 次或更少的操作得到目标数列，所以输出 $2$。

由 ChatGPT 4.1 翻译