注意:此问题的时限为 3 秒,是默认值的 1.5 倍。
You are given a length-N integer array a1,a2,…,aN (2≤N≤106,1≤ai≤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.
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) is replaced by min(10,3)=3 and (4,3) is replaced by max(4,3)=4.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The second line contains a1,a2,…,aN.
OUTPUT FORMAT (print output to the terminal / stdout):
The sum of the answer to the subproblem over all subarrays.
SAMPLE INPUT:
2
2 1
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
3
3 1 3
SAMPLE OUTPUT:
12
SAMPLE INPUT:
4
2 4 1 3
SAMPLE OUTPUT:
22
Consider the subarray [2,4,1,3].
1.Applying the first operation on (1, 3), our new array is [2,4,1].
2.Applying the second operation on (4, 1), our new array is [2,4].
3.Applying the third operation on (2, 4), our final number is 2.
It can be proven that 2 is the maximum possible value of the final number.
SCORING:
Inputs 4-5: N≤100
Inputs 6-7: N≤5000
Inputs 8-9: max(a)≤10
Inputs 10-13: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划

历年学员USACO获奖战绩一览
USACO 历年战绩
2026赛季战绩
- 5位铂金级
- 22位金级
- 25位银级
2024–2025赛季战绩
翰林考点及辅导学生
- 5位铂金级
- 25位金级
- 38位银级
2023–2024赛季战绩
- 8位铂金级
- 32位金级
- 37位银级
2022–2023赛季战绩
- 10位铂金级
- 29位金级
- 71位银级
篇幅有限,仅展示部分年份战绩。





