Minimum Interval Increments to Unimodal Sequence

Given a sequence of integers \(A_1, A_2, \ldots, A_N\) of length \(N\), you are allowed to perform the following operation any number of times:

• Select an interval \([L,R]\) (with \(1 \le L \le R \le N\)) and increment every number in that interval by \(1\).

Let the sequence after all operations be \(B_1, B_2, \ldots, B_N\). The goal is to achieve a "unimodal" sequence, that is, there must exist an index \(k\) (\(1 \le k \le N\)) such that the first part \(B_1, B_2, \ldots, B_k\) is strictly increasing and the second part \(B_k, B_{k+1}, \ldots, B_N\) is strictly decreasing. Note that the index \(k\) represents the peak and is included in both parts.

Determine the minimum number of operations required.

In other words, you need to find nonnegative integers \(X_i\) (the number of extra increments applied to \(A_i\) to obtain \(B_i = A_i + X_i\)) that can be achieved using contiguous-increment operations. It is known that given a final increase array \(X_1, X_2, \ldots, X_N\), the minimum number of operations necessary is:

\[ \text{cost} = X_1 + \sum_{i=2}^{N}\max(0, X_i - X_{i-1}). \]

Your task is to choose the increments so that \(B\) becomes unimodal and the total cost (i.e. the total number of operations) is minimized.

Note: You are only allowed to increase numbers (i.e. you cannot decrement any element).

inputFormat

The first line contains a single integer \(N\) (the length of the sequence).
The second line contains \(N\) space‐separated integers \(A_1, A_2, \ldots, A_N\).

outputFormat

Output a single integer representing the minimum number of operations required to turn the sequence into a unimodal sequence as described.

sample

3
1 2 1

0