Sum of Subarray Minimums

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr.

Input

• weights: an array of integers

Output

the sum of subarray minimums

Examples

Example 1:

Input:

weights = [1, 3, 2]

Output: 10

Explanation:

The sum of subarray minimums is 1+3+2+1+2+1=10.

Try it yourself