PermutacioN#12853

PermutacioN

1 segundo
256 megabytes
Muy difícil

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

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

Entrada

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 .

Salida

Imprime .

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Nota

El primer ejemplo se explica en el enunciado.