Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$, escriba un programa que realice la siguiente consulta:

• i j: Imprima la cantidad de enteros distintos en $A_i, A_{i+1}, \ldots, A_j$.

Entrada

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

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

La tercera línea contiene la cantidad $M$ de consultas ($1 \le M \le 100{,}000$).

La cuarta línea hasta la $M$-ésima línea contienen cada una una consulta $i, j$ ($1 \le i \le j \le N$).

Salida

Para cada consulta, imprima la respuesta en una línea separada.

Ejemplos

Entrada 1

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

Salida 1

3
2
3