Count Maximum Profitable Groups

Count the non-empty contiguous subarrays whose first or last element equals the maximum of the subarray. Equal and repeated values are allowed, and a range that satisfies both ends is counted only once.

输入格式

The first line contains n and the second line contains n prices. The original bounds are 1≤n≤500000, 1≤a[i]≤10^8.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
3 1 3 5

输出：

10

样例 2

输入：

3
1 5 2

输出：

5

样例 3

输入：

3
3 1 3

输出：

6

样例说明

The outputs of the three public examples are 10; 5; and 6, checked by independent enumeration or direct simulation.