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 & Output

Input

weights — an array of integers

Output

the sum of subarray minimums

Example

Input

weights = [1, 3, 2]

Output

Explanation

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

Try it yourself