Problems
You are given a length‑N integer array a₁, a₂, …, a_N (2 ≤ N ≤ 10⁶, with 1 ≤ aᵢ ≤ N). For every contiguous subarray of a (a total of N(N+1)/2 subarrays), solve the following subproblem and output the sum of the answers.
Subproblem:
Given a nonempty list of integers, alternate the following operations (starting with the first operation) until the list has size exactly one:
Operation 1: Replace two consecutive integers in the list with their minimum.
Operation 2: Replace two consecutive integers in the list with their maximum.
Determine the maximum possible value of the final remaining integer when these operations are performed optimally.
For example,
For [4, 10, 3]:
First, replace (10, 3) with min(10, 3)=3 → [4, 3]
Then, replace (4, 3) with max(4, 3)=4 → [4]For [3, 4, 10]:
First, replace (4, 10) with min(4, 10)=4 → [3, 4]
Then, replace (3, 4) with max(3, 4)=4 → [4]
Thus, the final number in both cases is 4.
Input
The first line contains an integer N.
The second line contains N space-separated integers a₁, a₂, …, a_N.
Output
Output the sum of the answers for the subproblem over all contiguous subarrays of a.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | |
| #2 | 20 | |
| #3 | 30 | |
| #4 | 40 | No additional constraints |
Example #1
2
2 1
4
For each subarray, the answers are:
[2] → final value is 2
[1] → final value is 1
[2, 1] → final value is 1
Thus, the total sum is 2 + 1 + 1 = 4.
Example #2
3
3 1 3
12
Example #3
4
2 4 1 3
22
For instance, consider the subarray [2, 4, 1, 3]:
Applying the first operation on (1, 3) gives [2, 4, 1].
Applying the second operation on (4, 1) gives [2, 4].
Applying the third operation on (2, 4) gives the final value 2.
It can be shown that 2 is the maximum possible final value for this subarray, and summing the answers over all subarrays yields 22.
You must sign in to write code.