Sum of Subarray Minimums

Given an array \(A\) of \(N\) integers, your task is to compute the sum of the minimum values of every contiguous subarray of \(A\). Since the result can be very large, output the answer modulo \(10^9+7\).

A subarray is a contiguous portion of the array. For example, if \(A = [3, 1, 2, 4]\), the subarrays are:

• [3]
• [3, 1]
• [3, 1, 2]
• [3, 1, 2, 4]
• [1]
• [1, 2]
• [1, 2, 4]
• [2]
• [2, 4]
• [4]

The minimum values for each of these subarrays are 3, 1, 1, 1, 1, 1, 1, 2, 2, 4 respectively, and their sum is \(17\).

Hint: An efficient way to solve this is to use a monotonic stack to find the previous less element (PLE) and next less element (NLE) for each element in the array. If the index of the current element is \(i\), and its PLE is at index \(j\) and NLE is at index \(k\), then the element \(A[i]\) appears as the minimum in \((i - j) \times (k - i)\) subarrays.

inputFormat

The first line contains a single integer \(N\), representing the number of elements in the array. The second line contains \(N\) space-separated integers which represent the elements of the array \(A\).

outputFormat

Output a single integer, which is the sum of the minimum values of all subarrays of \(A\) taken modulo \(10^9+7\).

4
3 1 2 4

17