Problem Description

Given a sequence \( A_i \) of length \( N \), you can perform multiple operations:

• Select an interval \([L, R]\) and increment all numbers in this interval by 1.

After these operations, let the resulting sequence be \( B_i \). You need to ensure that \( B_i \) satisfies the following condition:

• 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 determine the minimum number of operations required to meet this condition.

Input Format

The first line contains an integer \( N \) representing the length of the sequence.

The second line contains \( N \) integers \( A_i \) representing the sequence.

Output Format

Output a single integer representing the minimum number of operations.

Sample Input and Output

Sample Input #1

5
3 2 2 3 1

Sample Output #1

3

Sample Input #2

5
9 7 5 3 1

Sample Output #2

0

Sample Input #3

2
2021 2021

Sample Output #3

1

Sample Input #4

8
12 2 34 85 4 91 29 85

Sample Output #4

93

Notes

Sample 1 Explanation

• Perform an operation on \([2, 5]\), the sequence becomes \(\{3, 3, 3, 4, 2\}\).
• Perform an operation on \([2, 3]\), the sequence becomes \(\{3, 4, 4, 4, 2\}\).
• Perform an operation on \([3, 3]\), the sequence becomes \(\{3, 4, 5, 4, 2\}\).

Sample 2 Explanation

The sequence already meets the requirement; no operations are needed.

Sample 3 Explanation

Either perform an operation on \([1, 1]\) or \([2, 2]\).

Data Size and Constraints

This problem is bundled test.

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

For \( 100\% \) of the data, \( 1 \le N \le 2 \times 10^5 \), \( 1 \le A_i \le 10^9 \).

Notes

Translated from The 20th Japanese Olympiad in Informatics Final Round A Growing Vegetables is Fun 4.

见题面 Input 部分

见题面 Output 部分