~N~ people are waiting in line to enter a concert. People get bored waiting so they turn and look for someone familiar in the line.

Two persons ~A~ and ~B~ standing in line can see each other if they're standing right next to each other or if no person between them is strictly taller than person ~A~ or person ~B~.

Write a program that determines the number of pairs of people that can see each other.

Input Specification

The first line of input contains an integer ~N~ ~(1 \le N \le 500\,000)~, the number of people standing in line.
Each of the following ~N~ lines contains a single integer, the height of one person in nanometres.
Everyone will be shorter than ~2^{31}~ nanometres.
The heights are given in the order in which people are standing in line.

Output Specification

Output the number of pairs of people that can see each other on a single line.

Sample Input

7
2
4
1
2
2
5
1

Sample Output

10