题目描述

すぬけくん有一个长度为 $N$ 的整数序列 $x_1,x_2,\cdots,x_N$。最初，$x$ 的所有元素都是 $0$。

すぬけくん可以以任意顺序、任意次数进行以下两种操作：

• 操作 $1$：任选一个整数 $k$（$1 \leq k \leq N$），以及一个长度为 $k$ 的非负整数序列 $c_1,c_2,\cdots,c_k$，其中 $c$ 必须是广义单调递增的。然后，对于所有 $i$（$1 \leq i \leq k$），将 $x_i$ 替换为 $x_i + c_i$。
• 操作 $2$：任选一个整数 $k$（$1 \leq k \leq N$），以及一个长度为 $k$ 的非负整数序列 $c_1,c_2,\cdots,c_k$，其中 $c$ 必须是广义单调递减的。然后，对于所有 $i$（$1 \leq i \leq k$），将 $x_{N-k+i}$ 替换为 $x_{N-k+i} + c_i$。

すぬけくん的目标是使得对于所有 $i$，都有 $x_i = A_i$。请你求出他为了达成目标所需操作次数的最小值。

输入格式

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

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出すぬけくん为达成目标所需的最小操作次数。

样例 1

输入

5
1 2 1 2 1

输出

3

样例 2

输入

5
2 1 2 1 2

输出

2

样例 3

输入

15
541962451 761940280 182215520 378290929 211514670 802103642 28942109 641621418 380343684 526398645 81993818 14709769 139483158 444795625 40343083

输出

7

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入的所有值均为整数。

样例解释 1

例如，可以通过如下 $3$ 次操作达成目标，且少于 $3$ 次无法达成：

• 令 $k=2, c=(1,2)$，执行操作 $1$。操作后，$x=(1,2,0,0,0)$。
• 令 $k=3, c=(0,0,1)$，执行操作 $1$。操作后，$x=(1,2,1,0,0)$。
• 令 $k=2, c=(2,1)$，执行操作 $2$。操作后，$x=(1,2,1,2,1)$。

由 ChatGPT 4.1 翻译