Bessie's Game on Contiguous Segments

Bessie loves to play games on her mobile phone even though her large hooves make it rather tricky to use a small touch‐screen. In her favorite game, she starts with a sequence of N positive integers

\(a_1,a_2,\dots,a_N\) where \(2 \le N \le 262144\) and each \(a_i\) is in the range \(1\ldots10^6\). In one move, Bessie may choose two adjacent numbers and replace them with an integer which is strictly greater than the maximum of the two. For example, she may replace the adjacent pair \(5,7\) with \(8\). After exactly \(N-1\) moves the game ends with a single number. Bessie’s goal is to minimize this final number.

Your task is not only to play the game optimally on the entire sequence, but to play it optimally on every contiguous subarray of \(a\). For a given contiguous subarray, if its optimal play yields the final number \(F\) then it can be shown that

• If the subarray consists of a single element, then \(F=a_i\).
• If the subarray has at least two elements, then \(F=\max+1\) if the maximum element appears at one of the endpoints, and \(F=\max+2\) otherwise, where \(\max\) is the maximum value within that subarray.

Output the sum of the optimal final numbers over all contiguous subarrays of \(a\). (There are \(\frac{N(N+1)}{2}\) such subarrays.)

Note on how the final number is obtained: Every move replaces two adjacent numbers \(x\) and \(y\) with \(\max(x,y)+1\) (or a larger number if desired), so to minimize the final number, one should choose the minimal valid replacement and postpone increasing the maximum if possible. In a subarray, if the maximum occurs at one of the ends, it is possible to postpone its merge until the end (adding only 1), otherwise merging forces an extra increment (adding 2).

Your solution should compute the sum efficiently since a direct \(O(N^2)\) algorithm would be too slow given the constraints.

inputFormat

The first line contains a single integer \(N\) (the length of the sequence).
The second line contains \(N\) space‐separated positive integers \(a_1, a_2, \dots, a_N\), each in the range \(1\) to \(10^6\).

outputFormat

Output a single integer: the sum over all contiguous subarrays of the minimum final number that can be achieved by playing the game optimally.

sample

2
5 7

20