Calculate Region

The heights of a row of students are given in standing order. For each index i, consider all contiguous subarrays containing i in which heights[i] equals the maximum of the subarray (other students may be equally tall). The region of i is the longest length among these subarrays. Return the sum of the region lengths over all i. This is not the number of qualifying subarrays.

输入格式

The first line contains n, and the second line contains n integers heights[i]. The original problem's own complete ranges: 1≤n≤100000, 1≤heights[i]≤10^9.

输出格式

Output the exact integer sum. It can reach 10000000000, so 64-bit or arbitrary-precision integers are required; no modulus is taken.

样例 1

输入：

3
3 5 6

输出：

6

样例 2

输入：

3
1 2 1

输出：

5

样例 3

输入：

2
2 2

输出：

4

样例说明

In the original example [3,5,6], the region lengths are 1, 2, and 3, for a total of 6. An original note claimed the missing source image showed 5, but the formal Output and the explicit rules both give 6; this site discloses the conflict and keeps the formal output, which can be recomputed. In the original example [1,2,1], the lengths are 1, 3, and 1, for a total of 5; the original explanation mistakenly dropped the trailing 1 from the middle range, which should be [1,2,1]. The third example [2,2] is added by this site: both people can take the whole array, for a total of 4.