問題文

家庭菜園が趣味のビ太郎は自宅の庭でビバ草という植物を育てている. 庭には $N$ 株のビバ草が東西方向に一列に植えられており，西側から順に $1$ から $N$ までの番号が付いている. 現在，ビバ草 $i$ ($1 \leq i \leq N$) の背丈は $A_i$ である.

育てているビバ草は特別な品種改良の結果，水を与えるたびに背丈が $1$ 伸びる. ビ太郎は庭の見栄えを良 くするために水やりを複数回行い，以下の条件を満たすようにしたいと考えている．

• すべての水やりを行った後のビバ草 $i$ ($1 \leq i \leq N$) の背丈を $B_i$ とする．このとき，「$1 \leq j \leq k − 1$ に対し $B_j < B_{j+1}$」かつ「$k \leq j \leq N − 1$ に対し $B_j > B_{j+1}$」を満たすような整数 $k$ ($1 \leq k \leq N$) が存在する．

ただし，ビ太郎は不器用なため，$1$ 回の水やりにおいて，ある区間上のビバ草に一斉に水を与えることし かできない. すなわち，水やりを行うたびにある整数 $L$, $R$ ($1 \leq L \leq R \leq N$) を選び，ビバ草 $L, L + 1, \ldots , R$ に水を与える.

ビ太郎は水やりの回数をできるだけ少なくしたい．

ビバ草の数と現在の背丈の情報が与えられたとき，条件を満たすのに必要な水やりの回数の最小値を求め るプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

$N$
$A_1 \ldots A_N$

出力

必要な水やりの回数の最小値を，標準出力に $1$ 行で出力せよ．

5
3 2 2 3 1

3

5
9 7 5 3 1

0

2
2021 2021

1

8
12 2 34 85 4 91 29 85

93

制約

• $2 \leq N \leq 2 \times 10^5$．
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$)．

小課題

1. ($40$ 点) $N \leq 2000$．
2. ($60$ 点) 追加の制約はない．