P1823 [COI 2007] Patrik: Waiting at the Concert

$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.

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 a single line containing a number $s$, the total number of pairs of people who can see each other.

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