Oasis Reunion

Source: Baekjoon Online Judge

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ people standing in a line, each with a height. Two people can see each other if every person between them is no taller than the shorter of the two endpoints. Count the number of pairs that can see each other.

Input

The first line contains $N$. Each of the next $N$ lines contains one person height in queue order.

Output

Print the number of pairs of people that can see each other.

Subtasks

• Subtask 1 (20 points): $1\le N\le2000$; all other conditions are unchanged.
• Subtask 2 (30 points): $1\le N\le5\cdot10^5$ and all heights are pairwise distinct.
• Subtask 3 (50 points): $1\le N\le5\cdot10^5$, $1\le H_i<2^{31}$.

Examples

Input

7
2
4
1
2
2
5
1

Output

10

Explanation

Number the people from $1$ to $7$; their heights are $2,4,1,2,2,5,1$.

The visible pairs are:

(1,2), (2,3), (2,4), (2,5), (2,6), (3,4), (4,5), (4,6), (5,6), (6,7).

For example, people $2$ and $5$ have heights $4$ and $2$. The intermediate heights are $1$ and $2$, neither of which exceeds the shorter endpoint height $2$, so this pair is visible. In contrast, people $1$ and $3$ are not visible to each other because person $2$ between them has height $4$, which exceeds the shorter endpoint.

There are exactly $10$ valid pairs, so the program prints 10.