配点: 100 点
Bitaro 的爱好是家庭园艺,他在他的花园里种植了一种名为 Vivagusa 的植物。在花园里 N Viva草丛从西侧开始沿东西方向种植成一排。 它们的编号最大为 1 减去 N 。目前,维瓦古萨 i (1 \leqq i \leqq N) 的高度是 A_i 是。
由于特殊培育,我们种植的 Viva 草每次浇水都会长得更高。 1 拉伸。 Bitaro 希望多次浇水他的花园,使其看起来更好,并且他希望确保满足以下条件。
- 万岁草全部浇水后 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)存在。
然而,由于 Bitaro 很笨拙,1 浇水时,只能一次给特定区域的万岁草浇水。即每次浇水时的整数 L, R (1 \leqq L \leqq R \leqq N)并选择 Vivagusa。 给 L, L + 1, \ldots, R 喝水。
我想尽可能少地给 Bitaro 浇水。
给定 Viva 草的数量及其当前高度的信息,编写一个程序来查找满足条件所需的最少浇水次数。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
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).
小課題
- (40 点) N \leqq 2\,000.
- (60 点)没有额外的限制。
入力例 1
5 3 2 2 3 1
出力例 1
3
水如下。 执行 3 次即可满足该条件。
- L=2,R=5 饰演 Viva Grass 给 2, 3, 4, 5 喝水。维瓦草的高度是自西向西。 3, 3, 3, 4, 2 变为。
- L=2,R=3 饰演 Viva Grass 给 2, 3 喝水。维瓦草的高度是自西向西。 3, 4, 4, 4, 2 变为。
- L=3,R=3 饰演 Viva Grass 给 3 喝水。维瓦草的高度是自西向西。 3, 4, 5, 4, 2 变为。
2 浇水少于一次是不可能满足条件的,所以需要的最少次数为 3 是。
入力例 2
5 9 7 5 3 1
出力例 2
0
由于条件已满足,因此所需浇水的最少次数为 0 是。
入力例 3
2 2021 2021
出力例 3
1
满足一次浇水的条件,L = 1,R = 1 作为万岁草 给 1 喝水或 只需给L = 2,R = 2 作为万岁草 给 2 水即可。
入力例 4
8 12 2 34 85 4 91 29 85
出力例 4
93