Maximum Size Subarray Sum

For each position i in the array, find the length of the longest contiguous subarray that contains i and has a[i] as its maximum, forming an array b. Output the sum of all elements of b. The subarray may contain other maxima equal to a[i].

The standard input/output, the ranges added by this site, and the examples follow this problem's description.

输入格式

The first line contains n (this site's addition: 1≤n≤100000); the second line contains n integers (this site's addition: −10^9≤a[i]≤10^9). The original snapshot only gives n≤10^5 and no element range; the answer is output as a 64-bit integer.

输出格式

Output the sum of the longest subarray lengths over all positions, stored as a 64-bit integer.

样例 1

输入：

6
10 20 10 9 12 14

输出：

17

样例 2

输入：

2
5 5

输出：

4

样例 3

输入：

3
3 2 1

输出：

6