Jim and the Skyscrapers

Given an array $h_1,h_2,...,h_n$. Find the number of pairs of indices $(i,j)(1\le i<j\le n)$ that satisfy the following conditions: $h_i=h_j$ and $\underset{i<k<j}{\max }{h}_k\le h_j$.

Input

The first line contains one integer $n(1\le n\le 3\cdot 10^5)$. The second line contains $n$ integers $h_1,h_2,...,h_n(1\le h_i\le 10^6)$.

Output

Print the number of such pairs of indices.

Examples

In the first example, the desired pairs are: $(1,5),(1,6)(5,6)$ and $(2,4)$.