Problem Description

Bessie likes to download games to play on her phone, although she does find it rather difficult to use a small touchscreen with her big hooves.

She is especially obsessed with the game she is currently playing. The game starts with a sequence $a_1,a_2,\ldots,a_N$ of $N$ positive integers in the range $1\ldots 10^6$ ($2\le N\le 262,144$). In one move, Bessie can take two adjacent numbers and replace them with a single number that is greater than the maximum of the two numbers (for example, she can replace the adjacent pair $(5,7)$ with $8$). The game ends after $N-1$ moves, when only one number remains. The goal of the game is to minimize this final number.

Bessie knows this game is too easy for you. So your task is not only to play the game optimally on $a$, but to play it on every contiguous subarray of $a$.

Output the sum of the minimum possible final numbers over all $\frac{N(N+1)}{2}$ contiguous subarrays of $a$.

Input Format

The first line of input contains $N$.

The second line contains $N$ space-separated integers, representing the input sequence.

Output Format

Output one line containing the required sum.

6
1 3 1 2 1 10

115

Hint

There are a total of $\frac{6\cdot 7}{2}=21$ contiguous subarrays. For example, the minimum possible final number for the contiguous subarray $[1,3,1,2,1]$ is $5$, which can be achieved by the following sequence of operations:

Initial     -> [1,3,1,2,1]
Merge 1&3   -> [4,1,2,1]
Merge 2&1   -> [4,1,3]
Merge 1&3   -> [4,4]
Merge 4&4   -> [5]

Below are the minimum possible final numbers for each contiguous subarray:

final(1:1) = 1
final(1:2) = 4
final(1:3) = 5
final(1:4) = 5
final(1:5) = 5
final(1:6) = 11
final(2:2) = 3
final(2:3) = 4
final(2:4) = 4
final(2:5) = 5
final(2:6) = 11
final(3:3) = 1
final(3:4) = 3
final(3:5) = 4
final(3:6) = 11
final(4:4) = 2
final(4:5) = 3
final(4:6) = 11
final(5:5) = 1
final(5:6) = 11
final(6:6) = 10

[Subtask Properties]

• Testcases 2-3 satisfy $N\le 300$.
• Testcases 4-5 satisfy $N\le 3000$.
• In testcases 6-8, all values in the input sequence are at most $40$.
• In testcases 9-11, the input sequence is non-decreasing.
• Testcases 12-23 have no additional constraints.

Translated by ChatGPT 5