题目描述

给定一个长为 $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。