853. The Total of Every Stretch Minimum
Read n positive values. For every contiguous stretch, take its MINIMUM, and add all those
minima together. Print the total modulo 1000000007.
3 1 2 4 -> 17
11 81 94 43 3 -> 444
1 1 1 1 1 -> 15
For 3 1 2 4 the ten stretches have minima 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, which add to 17.
## Turning "for every stretch" into "for every value"
There are n(n+1)/2 stretches, which is 2 * 10^10 at the limit, so they cannot be visited. The
standard move is to swap the order of summation:
total = sum over stretches of ( minimum of that stretch )
= sum over positions i of a[i] * (how many stretches have a[i] as their minimum)
Each stretch contributes to exactly one position provided ties are broken, so the two sums are
equal. This is called a CONTRIBUTION argument, and it turns an impossible loop into n terms.
## The count, and the tie rule
Give each stretch to the EARLIEST position holding its minimum. Then position i owns a stretch
[l, r] exactly when l is past the last position at or below a[i], and r is before the
first later position strictly below a[i]:
count[i] = (i - previousSmallerOrEqual(i)) * (nextStrictlySmaller(i) - i)
total = sum of a[i] * count[i]
## Why one side is loose and the other strict, again
With both sides strict, a stretch whose minimum appears twice is counted by BOTH copies and the
total comes out too large. With both loose, it is counted by neither and the total comes out too
small. The row 1 1 1 1 1 answers 15; both-strict gives 20 and both-loose gives 5, so it is a
one-line test that catches the mistake.
## The stacks, and why they increase
Two passes. Left to right, pop while the top value is strictly greater than a[i]; the survivor
is previousSmallerOrEqual(i). Right to left, pop while the top is greater than or equal to
a[i]; the survivor is nextStrictlySmaller(i). Both stacks hold increasing values from the
bottom up, because both questions look for something SMALLER.
## Where it overflows
count[i] reaches 10^10 and a[i] reaches 10^9, so the raw product reaches 10^19, past
what a signed 64-bit integer holds. Reduce the count modulo 1000000007 BEFORE multiplying, and
reduce the value too. Then each product is below 10^18 and the running total stays inside 64
bits. Taking the remainder only at the very end is the standard way to get this wrong.
## Related problems
Problem 847 prints the counts themselves. Problem 854 runs this twice, once for minima and once for maxima. Problem 852 keeps only the right factor of the product.
## Cost
Time O(n), two stack passes and one multiply per position. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ a[i] ≤ 10^9` - print the answer modulo `1000000007`
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1].
Output
Print one integer alone on a line: the sum over all contiguous stretches of the stretch minimum, reduced modulo 1000000007. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.