题目描述

Snuke 有一个 $N$ 个整数的序列 $x_1,x_2,\cdots,x_N$。初始时，所有元素都是 $0$。

他可以任意次数任意顺序地进行以下两种操作：

• 操作 $1$：选择一个整数 $k$（$1 \leq k \leq N$）和一个非递减序列 $k$ 个非负整数 $c_1,c_2,\cdots,c_k$。然后，对于每个 $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$。然后，对于每个 $i$（$1 \leq i \leq k$），将 $x_{N-k+i}$ 替换为 $x_{N-k+i}+c_i$。

他的目标是使得对于所有 $i$，有 $x_i=A_i$。找出达成目标所需的最小操作次数。

约束条件

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

输入

输入通过标准输入给出，格式如下：

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

输出

打印达成 Snuke 目标所需的最小操作次数。

示例输入 1

5
1 2 1 2 1

示例输出 1

3

可以通过以下三个操作达到目标。无法使用少于三个操作来达到目标。

• 执行操作 $1$，选择 $k=2$，$c=(1,2)$。现在我们有 $x=(1,2,0,0,0)$。
• 执行操作 $1$，选择 $k=3$，$c=(0,0,1)$。现在我们有 $x=(1,2,1,0,0)$。
• 执行操作 $2$，选择 $k=2$，$c=(2,1)$。现在我们有 $x=(1,2,1,2,1)$。

示例输入 2

5
2 1 2 1 2

示例输出 2

2

示例输入 3

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

示例输出 3

7