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

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

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

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

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

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

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．

小課題

1. (40 点) N \leqq 2\,000．
2. (60 点) 追加の制約はない．

入力例 1

5
3 2 2 3 1

出力例 1

3

以下のように水やりを 3 回行うことで条件を満たすことができる．

• L=2，R=5 として，ビバ草 2, 3, 4, 5 に水を与える．ビバ草の背丈は西から順に 3, 3, 3, 4, 2 となる．
• L=2，R=3 として，ビバ草 2, 3 に水を与える．ビバ草の背丈は西から順に 3, 4, 4, 4, 2 となる．
• L=3，R=3 として，ビバ草 3 に水を与える．ビバ草の背丈は西から順に 3, 4, 5, 4, 2 となる．

2 回以下の水やりで条件を満たすことは不可能なので，必要な水やりの回数の最小値は 3 である．

入力例 2

5
9 7 5 3 1

出力例 2

0

すでに条件を満たしているため，必要な水やりの回数の最小値は 0 である．

入力例 3

2
2021 2021

出力例 3

1

1 回の水やりで条件を満たすためには，L = 1，R = 1 としてビバ草 1 に水を与えるか，または，L = 2，R = 2 としてビバ草 2 に水を与えればよい．

入力例 4

8
12 2 34 85 4 91 29 85

出力例 4

93