Soit une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$, écrire un programme qui répond aux requêtes suivantes :

• i j : Afficher le nombre d'entiers distincts dans $A_i, A_{i+1}, \ldots, A_j$.

Entrée

La première ligne contient la longueur $N$ de la séquence ($1 \le N \le 100{,}000$).

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

La troisième ligne contient le nombre $M$ de requêtes ($1 \le M \le 100{,}000$).

La quatrième ligne jusqu'à la $M$-ième ligne contiennent chacune une requête $i, j$ ($1 \le i \le j \le N$).

Sortie

Pour chaque requête, afficher la réponse sur une ligne distincte.

Exemples

Entrée 1

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

Sortie 1

3
2
3