Minimum-Weighted Subarray Sums¶

Estimated time limit: 1.5 seconds. Memory limit: 2048 MB.

The limit is 2 times the slowest median runtime of the reference program on the target platform, rounded up to a multiple of \(0.5\) seconds. See the evaluation environment.

Story¶

A report aggregates every contiguous segment of a sequence of readings. A segment contributes its minimum reading multiplied by its sum. Negative readings participate in both calculations.

(This story was rewritten by GPT-6.)

Formal Problem Statement¶

Given an integer sequence \(A_1,\ldots,A_N\) , compute

\[ \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). \]

Every nonempty contiguous subarray contributes once, including single-element subarrays. Print the exact integer without a modulus. The answer may be negative.

Input Format¶

The first line contains \(N\) . The second contains \(A_1,\ldots,A_N\) .

Output Format¶

Print the specified sum as one integer.

Samples¶

Sample 1¶

Input¶

7
3 4 2 -1 5 7 6

Output¶

Sample 2¶

Input¶

5
1 1 -1 1 1

Output¶

-1

Sample 3¶

Input¶

2
1000000000 1000000000

Output¶

4000000000000000000

Sample Explanation¶

The first sample has total contribution \(226\) . In the second, the totals for lengths one through five are \(5,4,-3,-4,-3\) , giving \(-1\) . In the third, each singleton contributes \(10^{18}\) , and the length-two subarray contributes \(2\times10^{18}\) .

Constraints and Guarantees¶

\(1\le N\le10^7\) , \(-10^9\le A_i\le10^9\) .

Score	Additional constraints
100%	None