Minimizing Trapped Rainwater via Single Elevation Modification

You are given a positive integer sequence (a = [a_1, a_2, \dots, a_n]) representing the elevation of the ground. After heavy rain, water will accumulate in depressions. The water trapped at index (i) in the original configuration is computed as [ w_i = \max\Big(\min( L[i], R[i] ) - a_i,;0\Big), ] where (L[i] = \max_{1\le j\le i}a_j) and (R[i] = \max_{i\le j\le n}a_j).

You are allowed to modify the elevation at exactly one index to any positive integer. In other words, you may choose one index (k) and change (a_k) to an arbitrarily large value (effectively (+\infty)). After the modification, for indices (i < k) the water becomes (w_i = L[i]-a_i) (since the right barrier becomes infinite), and for (i > k) it becomes (w_i = R[i]-a_i) (since the left barrier becomes infinite). At the modified index the water is zero.

Your task is to choose an index (k) (with (1 \le k \le n)) such that the total trapped water [ W = \sum_{\substack{i=1 \ i\neq k}}^{n} w_i ] is minimized. Output the minimum possible total water after the modification.

Note: All formulas are rendered in (\LaTeX).

inputFormat

The first line contains a single integer n (the length of the sequence).

The second line contains n positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer: the minimum total number of water units remaining after the optimal single modification.

sample

6
3 1 5 1 2 3

3