Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escribe un programa que procese las siguientes consultas:

• s e: Imprime la cantidad de pares $(i, j)$ tales que $s \le i < j \le e$ y $A_i > A_j$. ($1 \le s \le e \le N$)

Entrada

La primera línea contiene la longitud de la secuencia $N$ ($1 \le N \le 100{,}000$) y la cantidad de consultas $M$ ($1 \le M \le 100{,}000$).

La segunda línea contiene $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 1{,}000{,}000{,}000$)

Las siguientes $M$ líneas contienen cada una una consulta.

Salida

Para cada consulta, imprime su respuesta en una línea separada.

Ejemplos

Ejemplo de entrada 1

5 3
1 4 2 3 1
1 2
3 5
1 5

Ejemplo de salida 1

0
2
5