As a secretary, Rajan's job is to take attendance of people coming to major events. Today, there are n people lining up at the contest's offline location, numbered from the first to the last as 1 to n. The i-th person has the height of hi.

Two people i and j can see and talk to each other if there is no one with height >= min{hi, hj} standing between them. In other words, if everyone standing in between are shorter than i and j then they can have a conversation.

Rajan wonders how many pairs there are that can see each other. Help him find the answer so he can get back to work!

Input

- First line contains the integer n. (1<=n<=5*10^5)

- Second line contains n integers h1, h2, … , hn (for any i: hi <= 10^6) separated by space

Output

One integer which is the answer

Example 1:

Input:

6

2 1 4 3 6 5

Output:

7

Example 2:

Input:

5

2 2 2 2 2

Ouput:

4

Subtask:

- 50% of the test cases have n <= 100