C - Cola de Coppelia

Languages: C, C++, Java, JavaScript, Haskell, Tiger, Python, Pascal, C#
Time & Memory limits: (details)

En la cola de Coppelia hay $N$ personas (organizados de forma ideal en una línea). Después de estar horas de pie sin hacer nada la gente comenzó a buscar personas conocidas. Dos personas $A$ y $B$ que están en la cola se pueden ver entre sí, si están paradas una a continuación de la otra, o si entre ellas no hay nadie estrictamente mayor que alguna de las dos. Se pide calcular la cantidad de parejas de personas que se pueden ver en la cola.

Input

La primera línea contiene un entero $N$ $(1 \leq N \leq 500000)$ que representa la cantidad de personas en la cola.  Después habrán $N$ líneas, cada una con un entero $X$ $(0 \leq X \lt 2^{31})$, indicando la altura de cada una de las personas.

Output

La cantidad de parejas que se pueden ver entre sí en la cola.

Sample test(s)

Input
7 2 4 1 2 2 5 1
Output
10