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 翻译