Étant donné une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Écrire un programme pour traiter les requêtes suivantes :

• s e : Afficher le nombre de paires $(i, j)$ telles que $s \le i < j \le e$ et $A_i > A_j$. ($1 \le s \le e \le N$)

Entrée

La première ligne contient la longueur de la séquence $N$ ($1 \le N \le 100\,000$) et le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

La deuxième ligne contient $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 1\,000\,000\,000$)

Les $M$ lignes suivantes contiennent chacune une requête.

Sortie

Pour chaque requête, afficher sa réponse sur une ligne séparée.

Exemples

Exemple d'entrée 1

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

Exemple de sortie 1

0
2
5