# Jim and the Skyscrapers

Medium

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Given an array $h_{1},h_{2},...,h_{n}$. Find the number of pairs of indices $(i,j)(1≤i<j≤n)$ that satisfy the following conditions: $h_{i}=h_{j}$ and $i<k<jmax h_{k}≤h_{j}$.

## Input

The first line contains one integer $n(1≤n≤3⋅10_{5})$. The second line contains $n$ integers $h_{1},h_{2},...,h_{n}(1≤h_{i}≤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)$.

Input #1

Answer #1

Input #2

Answer #2

Submissions 15

Acceptance rate 7%