Para una permutación de los números del al , definimos de la siguiente manera: para cada par con 1 \le i \le j \le n, consideremos el par , donde es el menor de los números p_i, p_{i+1}, \ldots, p_j y es el mayor de ellos. Entonces es igual a la cantidad de pares distintos entre todos los \frac{n(n+1)}{2} pares.
Por ejemplo, consideremos la permutación (1, 3, 2).
Para el par , (min, max) = (1, 1)
Para el par , (min, max) = (1, 3)
Para el par , (min, max) = (1, 3)
Para el par , (min, max) = (3, 3)
Para el par , (min, max) = (2, 3)
Para el par , (min, max) = (2, 2)
En total hay pares distintos, por lo que f((1, 3, 2)) = 5.
Encuentra para la permutación dada (p_1, p_2, \ldots, p_n).
La primera línea contiene un entero (1 \le n \le 2\cdot 10^5).
La segunda línea contiene enteros p_1, p_2, \ldots, p_n (1 \le p_i \le n, todos los p_i son distintos dos a dos) — la permutación de longitud .
Imprime .
Ejemplo 1
Ejemplo 2
Ejemplo 3
El primer ejemplo se explica en el enunciado.