题目描述

译自 JOI 2021 Final T1「とてもたのしい家庭菜園 4 / Growing Vegetables is Fun 4」

Bitaro 喜欢园艺。他现在正在自己的花园种 Biba 草。在他的花园中共种有 $N$ 棵 Biba 草，从西向东种成一行。Biba 草自西向东从 $1$ 到 $N$ 编号。现在，第 $i$ 棵 Biba 草的高度是 $A_i$。

由于品种改良，如果 Bitaro 给一棵 Biba 草浇一次水，那么这棵 Biba 草的高度就增加 $1$。因为他想装饰他的花园，他会给这些 Biba 草浇若干次水，使其满足以下条件：

• 在 Bitaro 浇水后，令 $B_i$ 为第 $i$ 棵 Biba 草的高度。那么存在一个整数 $k\ (1\le k\le N)$，满足对于任意 $1\le j\le k-1$，都有 $B_j<B_{j+1}$，对于任意 $k\le j\le N-1$，都有 $B_j>B_{j+1}$。

然而，Bitaro 不擅长浇水。当他要给 Biba 草浇水时，他只能给在一段区间内的 Biba 草浇水。也就是说，他会选择两个整数 $L$ 和 $R$（$1\le L\le R\le N$）并且给第 $L,L+1,\ldots ,R$ 棵 Biba 草浇水。

Bitaro 想要最小化浇水的次数。

给出 Biba 草的棵数和它们目前的高度，写一个程序计算最少需要浇多少次水才能满足以上条件。

输入格式

第一行一个整数 $N$；

第二行 $N$ 个整数 $A_i$。

输出格式

输出一行一个整数，表示浇水的最少次数。

5
3 2 2 3 1

3

如果 Bitaro 按如下方法浇三次水，就可以满足条件：

• 令 $L=2,R=5$。Bitaro 会给第 $2,3,4,5$ 棵 Biba 草浇水。Biba 草的高度自西向东变为 $3,3,3,4,2$。

• 令 $L=2,R=3$。Bitaro 会给第 $2,3$ 棵 Biba 草浇水。Biba 草的高度自西向东变为 $3,4,4,4,2$。

• 令 $L=3,R=3$。Bitaro 会给第 $3$ 棵 Biba 草浇水。Biba 草的高度自西向东变为 $3,4,5,4,2$。

如果 Bitaro 浇水次数少于 $3$，则不可能满足条件。所以最少的浇水次数为 $3$。

5
9 7 5 3 1

0

因为本身就已经满足条件，所以最少浇水次数为 $0$。

2
2021 2021

1

Bitaro 选择 $L=1,R=1$ 给第 $1$ 棵 Biba 草浇水，或选择 $L=2,R=2$ 给第 $2$ 棵 Biba 草浇水都可以满足条件。

8
12 2 34 85 4 91 29 85

93

数据范围与提示

对于所有数据，$2\le N\le 2\times 10^5,1\le A_i\le 10^9$。

子任务附加限制及分值如下：

• 子任务 1（$40$ 分）：$N\le 2\ 000$；
• 子任务 2（$60$ 分）：无附加限制。