Concert Queue Vision

$n$ people are waiting in a queue to enter a concert. Bored with the wait, they start turning around to spot any acquaintances in the line.

For any two persons $a$ and $b$, they can see each other if either:

• They are adjacent.
• All the persons between them have heights no greater than min$\,(a, b)$ (i.e. there is no one between them who is taller than $a$ or $b$).

Write a program to compute the total number of pairs that can see each other.

inputFormat

The first line contains an integer $n$ ($1 \leq n \leq 500,000$), representing the number of people in the queue.

The second line contains $n$ integers, each representing the height of a person in the order of the queue.

outputFormat

Output a single integer representing the total number of pairs of people who can see each other.

sample

7
2 4 1 2 2 5 1

10