[AGC040E] Prefix Suffix Addition

你有一个长为 $N$ 的序列 $x_1,x_2,\dots,x_N$，一开始全部为 $0$，你现在可以以任意顺序进行任意次以下两种操作： 1. 选定整数 $k(1\le k\le N)$ 与不下降非负序列 $c_1,c_2,\dots,c_k$，对所有 $1\le i \le k$，令 $x_i$ 加上 $c_i$。 2. 选定整数 $k(1\le k\le N)$ 与不上升非负序列 $c_1,c_2,\dots,c_k$，对所有 $1\le i \le k$，令 $x_{N-k+i}$ 加上 $c_i$。 问最少进行多少次操作使得最后对任意 $i$ 有 $x_i=A_i$。

[problemUrl]: https://atcoder.jp/contests/agc040/tasks/agc040_e すぬけくんは，長さ $ N $ の整数列 $ x_1,x_2,\cdots,x_N $ を持っています． 最初，$ x $ の全ての要素は $ 0 $ です． すぬけくんは，以下の $ 2 $ 種類の操作を好きな順序で好きな回数行うことができます． - 操作 $ 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 $

すぬけくんが目標を達成するために行う操作回数の最小値を出力せよ．

5
1 2 1 2 1

3

5
2 1 2 1 2

2

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 $ - 入力される値はすべて整数である． ### Sample Explanation 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) $ となる．