AT_joi2021ho_a とてもたのしい家庭菜園 (Growing Vegetables is Fun 4)

[problemUrl]: https://atcoder.jp/contests/joi2021ho/tasks/joi2021ho_a 家庭菜園が趣味のビ太郎は自宅の庭でビバ草という植物を育てている．庭には $ 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 $ ($ 1\ \leqq\ k\ \leqq\ N $) が存在する． ただし，ビ太郎は不器用なため，$ 1 $ 回の水やりにおいて，ある区間上のビバ草に一斉に水を与えることしかできない．すなわち，水やりを行うたびにある整数 $ L,\ R $ ($ 1\ \leqq\ L\ \leqq\ R\ \leqq\ N $) を選び，ビバ草 $ L,\ L\ +\ 1,\ \ldots,\ R $ に水を与える． ビ太郎は水やりの回数をできるだけ少なくしたい． ビバ草の数と現在の背丈の情報が与えられたとき，条件を満たすのに必要な水やりの回数の最小値を求めるプログラムを作成せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $ N $ $ A_1 $ $ \cdots $ $ A_N $

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

### 制約 - $ 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 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 以下のように水やりを $ 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 $ である． - - - - - - ### Sample Explanation 2 すでに条件を満たしているため，必要な水やりの回数の最小値は $ 0 $ である． - - - - - - ### Sample Explanation 3 1 回の水やりで条件を満たすためには，$ L\ =\ 1 $，$ R\ =\ 1 $ としてビバ草 $ 1 $ に水を与えるか，または，$ L\ =\ 2 $，$ R\ =\ 2 $ としてビバ草 $ 2 $ に水を与えればよい． - - - - - -