Problem Description

Given a sequence $A$ of length $N$, you may perform the following operation any number of times:

• Choose an interval $[L, R]$ and add $1$ to every number in this interval.

Let the sequence after these operations be $B$. You need to make $B$ satisfy the following requirement:

• There exists an integer $k \in [1, N]$ such that the subsequence $A_1 = \{B_1, B_2, \cdots, B_k\}$ is strictly increasing, and the subsequence $A_2 = \{B_k, B_{k+1}, \cdots, B_N\}$ is strictly decreasing.

You want to know the minimum number of operations needed to satisfy the requirement above.

Input Format

The first line contains an integer $N$, representing the length of the sequence.

The second line contains $N$ integers, representing the sequence $A$.

Output Format

Output one integer in one line, representing the minimum number of operations.

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

Hint

Explanation for Sample 1

• Perform the operation on $[2, 5]$, and the sequence becomes $\{3, 3, 3, 4, 2\}$.
• Perform the operation on $[2, 3]$, and the sequence becomes $\{3, 4, 4, 4, 2\}$.
• Perform the operation on $[3, 3]$, and the sequence becomes $\{3, 4, 5, 4, 2\}$.

Explanation for Sample 2

The sequence already satisfies the requirement, so no operation is needed.

Explanation for Sample 3

It is enough to perform the operation on interval $[1, 1]$ or $[2, 2]$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (40 pts): $N \le 2000$.
• Subtask 2 (60 pts): No additional constraints.

For $100\%$ of the testdata, $1 \le N \le 2 \times 10^5$, $1 \le A_i \le 10^9$.

Notes

Translated from the English statement of The 20th Japanese Olympiad in Informatics Final Round A とてもたのしい家庭菜園 4, Growing Vegetables is Fun 4.

Translated by ChatGPT 5