Sum of Subarray Regions

The region of each position is the longest contiguous interval that contains the position and in which its height is still the maximum; equal heights still count as the maximum.

The standard input/output conventions and constraints added by this site are described under "Input".

输入格式

n≤100000, heights 1..10^9.

输出格式

Output the sum of the lengths of all regions.

样例 1

输入：

3
3 5 6

输出：

6

样例 2

输入：

2
5 5

输出：

4

样例 3

输入：

3
2 1 2

输出：

7

样例 4

输入：

4
1 3 2 4

输出：

9