Min Max Subarrays

시간 제한3초메모리 제한2048 MB

요약

모든 연속 부분 배열에 대해 인접한 두 수를 최소, 최대 연산으로 번갈아 합쳐 마지막에 남을 수 있는 값의 최댓값을 구하고, 그 값들의 합을 출력한다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 그리디, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

You are given a length- $N$ integer array $a\_1,a\_2,\dots,a\_N$ ( $2\le N\le 10^6, 1\le a\_i\le N$ ). Output the sum of the answers for the subproblem below over all $N(N+1)/2$ contiguous subarrays of $a$ .

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

Replace two consecutive integers in the list with their minimum.
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)$ is replaced by $\min(10, 3)=3$ and $(4, 3)$ is replaced by $\max(4, 3)=4$ .

입력

The first line contains $N$ .

The second line contains $a\_1,a\_2,\dots,a\_N$ .

출력

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

예제3

예제 1
입력
```
2
2 1
```
예상 출력
```
4
```
예제 2
입력
```
3
3 1 3
```
예상 출력
```
12
```
예제 3
입력
```
4
2 4 1 3
```
예상 출력
```
22
```