620. Sum of Subarray Maximums

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

Input: JSON {arr}.

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

Examples

Example 1

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

Example 2

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

Example 3

Input: {"arr":[11,81,94,43,3]}
Output: 1108
Explanation: Weighted maxima summed.