Find Maximum Number of Balanced Combinations

Following the source's enumeration, a combination means a non-empty contiguous subarray. A combination is balanced if its last item is not the maximum of the subarray, that is, some earlier number is strictly greater. Find the total number of balanced combinations; combinations may overlap.

输入格式

The first line contains n, and the second line contains n integers. This site sets 1≤n≤200000 and elements in −10^9..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

3
3 6 3

输出：

2

样例 2

输入：

2
3 3

输出：

0

样例 3

输入：

3
5 4 3

输出：

3

样例说明

Example 1: [3,6,3] and [6,3] are balanced, 2 in total. Example 2: the last item of every segment is tied for the maximum and no element is strictly greater, so the answer is 0. Example 3: all three contiguous segments of length ≥2 are balanced, so the answer is 3.