Leaning Lantern Frames

Time limit: 2000 msMemory limit: 256 MB

In the Lantern Arcade there are $N$ lanterns in a straight row, indexed $1$ through $N$ from left to right. The height of lantern $i$ is $H_i$ .

A camera frame is a contiguous group of lanterns, described by two indices $L$ and $R$ with $1 \le L \le R \le N$ . Inside the frame, let $M$ be the maximum height among .

The frame is called leaning if both conditions hold:

there is exactly $1$ index $P$ with $L \le P \le R$ and $H_P = M$ ;

Count how many camera frames are leaning.

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of lanterns. The second line contains $N$ space-separated integers (), the heights of the lanterns in left-to-right order. Lanterns are indexed through in the order given.

Output

Print $1$ integer on $1$ line: the number of leaning camera frames.

Samples

Sample 1

Input

5
3 1 4 2 5

Output

The leaning frames are $[1, 1]$ , $[1, 2]$ , $[2, 2]$ , $[2, 4]$ , , , , and .

Leaning Lantern Frames

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2