619. Sum of Subarray Minimums

Given an array arr, return the sum of the minimum element of every contiguous subarray, taken modulo 1000000007. The input is JSON {arr}.

Input: JSON {arr}.

Output: Integer — the sum of subarray minimums, modulo 1e9+7.

Examples

Example 1

Input: {"arr":[3,1,2,4]}
Output: 17
Explanation: Sum of all subarray minimums.

Example 2

Input: {"arr":[5]}
Output: 5
Explanation: One subarray.

Example 3

Input: {"arr":[11,81,94,43,3]}
Output: 444
Explanation: Weighted minima.