Description

$n$ people are standing in a queue to enter a concert. People are bored, so they start turning around to look for their acquaintances in the line.

For any two people $a$ and $b$ in the queue, they can see each other if they are adjacent, or if there is no one between them who is taller than both $a$ and $b$.

Write a program to compute how many pairs of people can see each other.

Input Format

The first line contains an integer $n$, the number of people in the queue.

Each of the next $n$ lines contains an integer, the height of a person, in nanometers (equal to $10^{-9}$ meters). These heights correspond to the people in the queue.

Output Format

Output a single line containing a number $s$, the total number of pairs of people who can see each other.

7 
2 
4 
1 
2 
2 
5 
1

10

Hint

Constraints

For all test points, $1 \le$ each person’s height $< 2^{31}$, and $1 \le n \le 5 \times 10^5$.

Translated by ChatGPT 5