8912: YACS - IAI 2023年8月月赛乙组 T4 —— 极值的和
[Creator : ]
Description
给定一个序列 $a_1,a_2,a_3,…,a_n$，请求出该序列每一个连续子序列的最大值，并计算这些最大值的和。
也就是求出 $\sum_{1≤i≤j≤n}\text{max}\{a_i,a_{i+1},⋯,a_j\}$。
也就是求出 $\sum_{1≤i≤j≤n}\text{max}\{a_i,a_{i+1},⋯,a_j\}$。
Input
第一行：单个整数 $n$。
第二行：$n$ 个整数表示 $a_1,a_2,…,a_n$。 Output
单个整数：表示所有区间最大数的和
Constraints
对于 30% 的数据，$1≤n≤500$
对于 60% 的数据，$1≤n≤50,000$
对于 100% 的数据，$1≤n≤500,000$
$0≤a_i≤1,000,000$
对于 60% 的数据，$1≤n≤50,000$
对于 100% 的数据，$1≤n≤500,000$
$0≤a_i≤1,000,000$
Sample 1 Input
4
3 2 4 3
Sample 1 Output
35
（1）第一个元素 3 作为最大值的区间有 [1,1],[1,2]，共 2 个，则这个 3 对答案的贡献为 3×2=6；
（2）第二个元素 2 作为最大值的区间有 [2,2]，共 1 个，则这个 2 对答案的贡献为 2×1=2；
（3）第三个元素 4 作为最大值的区间有 [3,3],[2,3],[1,3],[3,4],[2,4],[1,4]，共 6 个，则这个 4 对答案的贡献为 4×6=24；
（4）第四个元素 3 作为最大值的区间有 [4,4]，共 1 个，则这个 3 对答案的贡献为 3×1=3；
最终答案即为上述贡献之和：6+2+24+3=35。
（2）第二个元素 2 作为最大值的区间有 [2,2]，共 1 个，则这个 2 对答案的贡献为 2×1=2；
（3）第三个元素 4 作为最大值的区间有 [3,3],[2,3],[1,3],[3,4],[2,4],[1,4]，共 6 个，则这个 4 对答案的贡献为 4×6=24；
（4）第四个元素 3 作为最大值的区间有 [4,4]，共 1 个，则这个 3 对答案的贡献为 3×1=3；
最终答案即为上述贡献之和：6+2+24+3=35。
Sample 2 Input
3
4 5 6
Sample 2 Output
32
Sample 3 Input
2
8 6
Sample 3 Output
22
3
6 5 4
32
Sample 4 Input
2
6 8
Sample 4 Output
22
6 + 8 + 8 = 22
HINT
相同题目：IAI月赛。