最小值加权的区间和¶
预估时间限制：1.5 秒。内存限制：2048 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一份读数报告需要统计所有连续片段。每个片段的贡献等于它的最小读数乘以读数总和；负读数也参与计算。
(本故事由GPT-6重写)
形式化问题描述¶
给定长度为 \(N\) 的整数序列 \(A_1,\ldots,A_N\) ，求
\[
\sum_{1\le L\le R\le N}\left(\min_{L\le i\le R}A_i\right)\left(\sum_{i=L}^{R}A_i\right).
\]
每个非空连续子区间恰好贡献一次，包括长度为一的区间。输出精确整数，不取模；答案可能为负数。
输入格式¶
第一行一个整数 \(N\) .第二行 \(N\) 个整数 \(A_1,\ldots,A_N\) .
输出格式¶
输出一行一个整数，表示上述总和。
样例¶
样例 1¶
输入¶
7
3 4 2 -1 5 7 6
输出¶
226
样例 2¶
输入¶
5
1 1 -1 1 1
输出¶
-1
样例 3¶
输入¶
2
1000000000 1000000000
输出¶
4000000000000000000
样例解释¶
第一组所有区间的贡献之和为 \(226\) .第二组按区间长度一到五汇总的贡献分别为 \(5,4,-3,-4,-3\) ，总和为 \(-1\) .第三组的两个单点各贡献 \(10^{18}\) ，长度二的区间贡献 \(2\times10^{18}\) .
数据范围与保证¶
\(1\le N\le10^7\) , \(-10^9\le A_i\le10^9\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |