| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 10 | 5 | 3 | 60.000% |
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.
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.
2 2 1
4
The answer for $[2]$ is 2ドル,ドル the answer for $[1]$ is 1ドル,ドル and the answer for $[2, 1]$ is 1ドル$.
Thus, our output should be 2ドル+1+1 = 4$.
3 3 1 3
12
4 2 4 1 3
22
Consider the subarray $[2, 4, 1, 3]$.
It can be proven that 2ドル$ is the maximum possible value of the final number.