Sum of Subarray Minimums

Given an array of integers, your task is to compute the sum of the minimum values of every subarray of the array. A subarray is defined as a contiguous sequence of elements within the array. The final result should be computed modulo \(10^9 + 7\).

For instance, consider the array [3, 1, 2, 4]. The subarrays and their minimum values are as follows:

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

The sum of these minimum values is 17. Your solution should work efficiently for large arrays.

inputFormat

The first line contains a single integer (n), representing the size of the array. The second line contains (n) space-separated integers which represent the elements of the array.

outputFormat

Output a single integer — the sum of the minimum values of all subarrays, computed modulo (10^9 + 7).## sample

4
3 1 2 4

17