[JOI 2021 Final] とてもたのしい家庭菜園 4

给定一个长为 $N$ 的序列 $A_i$，你可以进行若干次操作： - 选定一个区间 $[L,R]$，让这个区间里的数加 $1$。 设经过这若干次操作后的序列为 $B_i$，那么你需要让 $B_i$ 满足下面这个要求： - 存在一个整数 $k \in [1,N]$，满足对于子序列 $A_1=\{A_1,A_2,\cdots,A_k\}$ 为严格递增序列，对于子序列 $A_2=\{A_k,A_{k+1},\cdots,A_N\}$ 为严格递减序列。 你想知道最少需要多少次操作才能满足上面这个要求。

第一行一个整数 $N$ 代表序列长度。 第二行 $N$ 个整数 $A_i$ 代表序列。

一行一个整数代表最小操作次数。

5
3 2 2 3 1

3

5
9 7 5 3 1

0

2
2021 2021

1

8
12 2 34 85 4 91 29 85

93

#### 样例 1 解释 - 对 $[2,5]$ 进行操作，序列变为 $\{3,3,3,4,2\}$。 - 对 $[2,3]$ 进行操作，序列变为 $\{3,4,4,4,2\}$。 - 对 $[3,3]$ 进行操作，序列变为 $\{3,4,5,4,2\}$。 #### 样例 2 解释 序列已经满足要求，不需要操作。 #### 样例 3 解释 对区间 $[1,1]$ 或 $[2,2]$ 进行操作都可。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（40 pts）：$N \le 2000$。 - Subtask 2（60 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$1 \le A_i \le 10^9$。 #### 说明 翻译自 [The 20th Japanese Olympiad in Informatics Final Round A とてもたのしい家庭菜園 4 的英文翻译 Growing Vegetables is Fun 4](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t1-en.pdf)。