题目描述

Bitaro 给定一个长为 $N$ 的序列 $A$，你可以进行若干次操作：

• 选定一个区间 $[L,R]$，让这个区间里的数加 $1$。

设经过这若干次操作后的序列为 $B$，那么你需要让 $B$ 满足下面这个要求：

• 存在一个整数 $k \in [1,N]$，满足对于子序列 $A_1=\{B_1,B_2,\cdots,B_k\}$ 为严格递增序列，对于子序列 $A_2=\{B_k,B_{k+1},\cdots,B_N\}$ 为严格递减序列。

你想知道最少需要多少次操作才能满足上面这个要求。

输入格式

第一行一个整数 $N$；

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

输出格式

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

5
3 2 2 3 1

如果 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$.

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$ 分）：无附加限制。