Problem
On vous donne un tableau d'entiers A de longueur n.
Il faut répondre à m requêtes de la forme "rapporter le nombre de nombres différents du sous-segment du tableau A de l'élément d'indice l à l'élément d'indice r" (les deux limites du sous-segment sont incluses, le tableau est numéroté à partir de un).
Saisie :
La première ligne contient deux nombres : n - le nombre d'éléments du tableau et m - le nombre de requêtes (1 <= n, m <= 10
5).
La deuxième ligne contient n entiers A
i - éléments de tableau (0 <= A
i <= 10
6).
Ensuite, m lignes sont données, chacune contenant deux nombres l et r - les limites du sous-segment pour chaque requête (1 <= l <= r <= n).
Sortie :
Sur une seule ligne, imprimez m nombres séparés par des espaces - pour chaque requête, le nombre de nombres différents sur le sous-segment correspondant.
Exemple :
| Entrée |
Sortie |
7 5
1 3 1 2 2 4 1
1 3
4 5
37
24
77 |
2 1 3 3 1 |