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

家庭菜園が趣味のビ太郎は自宅の庭でビバ草という植物を育てている. 庭にはN 株のビバ草が東西方向に
一列に植えられており,西側から順に1 からN までの番号が付いている. 現在,ビバ草i (1 ≦i ≦N) の背丈
はAi である.
育てているビバ草は特別な品種改良の結果,水を与えるたびに背丈が1 伸びる. ビ太郎は庭の見栄えを良
くするために水やりを複数回行い,以下の条件を満たすようにしたいと考えている.
• すべての水やりを行った後のビバ草i (1 ≦i ≦N) の背丈をBi とする.このとき,「1 ≦j ≦k −1 に対
しBj < Bj+1」かつ「k ≦j ≦N −1 に対しBj > Bj+1」を満たすような整数k (1 ≦k ≦N) が存在する.
ただし,ビ太郎は不器用なため,1 回の水やりにおいて,ある区間上のビバ草に一斉に水を与えることし
かできない. すなわち,水やりを行うたびにある整数L, R (1 ≦L ≦R ≦N) を選び,ビバ草L, L + 1, . . . , R に
水を与える.
ビ太郎は水やりの回数をできるだけ少なくしたい.
ビバ草の数と現在の背丈の情報が与えられたとき,条件を満たすのに必要な水やりの回数の最小値を求め
るプログラムを作成せよ.

• 2 ≦N ≦200 000.
• 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).

第20 回日本情報オリンピック(JOI 2020/2021) 本選
2021 年2 月14 日(オンライン開催)

1. (40 点) N ≦2 000.
2. (60 点) 追加の制約はない.

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

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

생성자가 기록되지 않았습니다.

출처 JOI 2021 Final