Sum of Max of Subarrays

Every non-empty contiguous subarray contributes its maximum multiplied by its length; find the sum of all contributions. Negative numbers are allowed, and the answer must be output exactly, without any modulus; a linear-time algorithm is required.

输入格式

The first line contains n and the second line contains n integers. On this site 0≤n≤200000 and elements are in −10^9..10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
4 2 1 2

输出：

59

样例 2

输入：

3
-3 -1 -1

输出：

-12

样例 3

输入：

0

输出：

0

样例说明

The outputs of the three public examples are 59; -12; and 0, checked by independent enumeration or direct simulation.