P7404 [JOI 2021 Final] Interesting Home Garden 4 / Growing Vegetables is Fun 4

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.

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

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

#### 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](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t1-en.pdf). Translated by ChatGPT 5