Problem
Soit une permutation de n éléments.
Répondez à m requêtes sur le nombre d'inversions pour un sous-segment de permutation de l à r.
Une inversion est une paire d'indices i, j tels que i < j et a
i > ; a
j, où a
i est le i-ème élément de la permutation.
Saisie :
La première ligne contient le nombre n (1 <= n <= 10
5).
La deuxième ligne contient une permutation de n éléments (les éléments de la permutation sont des entiers deux à deux distincts de 1 à n).
La troisième ligne contient le nombre m (1 <= m <= 10
5).
Les m lignes suivantes contiennent deux entiers l et r - les bornes de la requête (1 <= l, r <= n).
Sortie :
Imprimer m lignes - les réponses à ces questions.
Exemples :
| Entrée |
Sortie |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |