Subarray Sum Range
Given an array of N integers, find the sum of the minimums of all possible contiguous subarrays. A contiguous subarray is defined by its start and end indices (inclusive). For example, in the array [3, 1, 2, 4], the subarrays are [3], [1], [2], [4], [3, 1], [1, 2], [2, 4], [3, 1, 2], [1, 2, 4], and [3, 1, 2, 4]. The sum of minimums is 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17. Since the sum can be very large, print the answer modulo 10^9 + 7.
Input
The first line contains an integer N, the size of the array. The second line contains N space-separated integers representing the array elements.
Output
Print a single integer, the sum of minimums of all contiguous subarrays modulo 10^9 + 7.
Constraints
1 <= N <= 200000 1 <= A[i] <= 10^9
Example 1
4 3 1 2 4
17
The subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum = 17.
Example 2
3 1 1 1
6
Subarrays: [1], [1], [1], [1,1], [1,1], [1,1,1]. Minimums: 1, 1, 1, 1, 1, 1. Sum = 6.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 3 1 2 4
3 1 1 1