TALKPAIRS - Rajan and the talking pairs

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


Added by:LTU ComSoc
Date:2022-04-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.