Sum of Minimums of All Subarrays
MediumPractice library · +20 XPstackmonotonic stackprefix sum
Given an array of integers arr, find the sum of the minimums of all possible contiguous subarrays of arr. Since the answer may be large, return the answer modulo 10^9 + 7.
A subarray is a contiguous part of an array.
Input
The first line contains an integer N, the size of the array. The second line contains N integers representing the array elements.
Output
Print a single integer, the sum of minimums of all subarrays modulo 10^9 + 7.
Constraints
1 <= N <= 200000 1 <= arr[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
3 1 2 3
Output
10
Subarrays are [1], [2], [3], [1,2], [2,3], [1,2,3]. Minimums are 1, 2, 3, 1, 2, 1. Sum = 1+2+3+1+2+1 = 10.
Example 2
Input
4 3 1 2 4
Output
17
Subarrays and minimums: [3]->3, [1]->1, [2]->2, [4]->4, [3,1]->1, [1,2]->1, [2,4]->2, [3,1,2]->1, [1,2,4]->1, [3,1,2,4]->1. Sum = 3+1+2+4+1+1+2+1+1+1 = 17.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
3 1 2 3
Example 2 input
4 3 1 2 4