Skip to content
Sign in

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

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
512 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

家庭菜園が趣味のビ太郎は自宅の庭でビバ草という植物を育てている．庭には \(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\) に水を与える．

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

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

Input

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

\(N\)
\(A_1\) \(\cdots\) \(A_N\)

Output

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

Constraints

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

Subtasks

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

Examples

Sample input 1
5
3 2 2 3 1
Sample output 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\) である．

Sample input 2
5
9 7 5 3 1
Sample output 2
0

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

Sample input 3
2
2021 2021
Sample output 3
1

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

Sample input 4
8
12 2 34 85 4 91 29 85
Sample output 4
93

Notes

JOI 2021 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source