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

家庭菜园爱好者比太郎在自家院子里种植了一种叫做“比巴草”的植物。院子里共有 $N$ 株比巴草，沿东西方向排成一行，从西侧开始依次编号为 $1$ 到 $N$。当前，第 $i$ 株比巴草（$1 \leq i \leq N$）的高度为 $A_i$。 由于经过特殊品种改良，每次浇水后，比巴草的高度会增加 $1$。比太郎为了让院子的观赏性更好，打算多次浇水，使得最终满足以下条件： - 经过所有浇水后，第 $i$ 株比巴草的高度为 $B_i$。此时，存在一个整数 $k$（$1 \leq k \leq N$），使得“对于 $1 \leq j \leq k-1$，有 $B_j < B_{j+1}$”且“对于 $k \leq j \leq N-1$，有 $B_j > B_{j+1}$”。 也就是说，最终高度序列 $B$ 存在一个峰值点 $k$，使得从左到 $k$ 单调递增，从 $k$ 到右端单调递减。 但比太郎手笨，每次只能选择一个区间 $L, R$（$1 \leq L \leq R \leq N$），同时给区间内的所有比巴草浇水一次。 比太郎希望浇水的次数尽可能少。 给定比巴草的数量和当前高度，请编写程序，求满足条件所需的最小浇水次数。

输入为一行，包含 $N$ 和 $A_1, A_2, \ldots, A_N$，均为整数。

输出满足条件所需的最小浇水次数。

## 限制 - $2 \leq N \leq 200\,000$。 - $1 \leq A_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 ## 子任务 1.（40 分）$N \leq 2\,000$。 2.（60 分）无额外限制。 ## 样例解释 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$。 ## 样例解释 2 初始状态已经满足条件，因此最小次数为 $0$。 ## 样例解释 3 只需一次浇水即可满足条件，可以选择 $L=1,R=1$ 给第 $1$ 株浇水，或 $L=2,R=2$ 给第 $2$ 株浇水。 由 ChatGPT 4.1 翻译