Min Max Subarrays

문제

You are given a length-$NN$ integer array $a_1,a_2,\dots ,a_{N}a\_1,a\_2,\backslash dots,a\_N$ ($2\le N\le {10}^6,1\le a_i\le N2\backslash le\; N\backslash le\; 10^6,\; 1\backslash le\; a\_i\backslash le\; N$). Output the sum of the answers for the subproblem below over all $N(N+1)\mathrm{/}2N(N+1)/2$ contiguous subarrays of $aa$.

Given a nonempty list of integers, alternate the following operations (starting with the first operation) until the list has size exactly one.

1. Replace two consecutive integers in the list with their minimum.
2. Replace two consecutive integers in the list with their maximum.

Determine the maximum possible value of the final remaining integer.

For example,

[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]

In the first array, $(10,3)(10,\; 3)$ is replaced by $\min (10,3)=3\backslash min(10,\; 3)=3$ and $(4,3)(4,\; 3)$ is replaced by $\max (4,3)=4\backslash max(4,\; 3)=4$.

입력

The first line contains $NN$.

The second line contains $a_1,a_2,\dots ,a_{N}a\_1,a\_2,\backslash dots,a\_N$.

출력

The sum of the answer to the subproblem over all subarrays.

2
2 1

4

3
3 1 3

12

4
2 4 1 3

22