Matcom Online Grader

Dada una secuencia de números enteros $a_1, a_2,…, a_n$  se quiere saber dado los índices $(i,j)$ $(1 \le i \le j \le n)$ la cantidad de elementos diferentes en la secuencia $a_i, …, a_j$.

Input

Línea 1 : $n$ $(1 \le n \le 30000)$, la cantidad de elementos de la secuencia.
Línea 2 : $n$ números $a_1, a_2,…, a_n$ $(1 \le a_i \le 10^6)$, representa la secuencia.
Línea 3 : $P$ $(1 \le P \le 200000)$ cantidad de consultas que se van a efectuar.
En las próximas $P$ líneas por cada línea hay dos enteros $i$ y $j$ separados por un espacio $(1 \le i \le j \le n)$ que representan las consultas.

Output

Por cada consulta se imprime en una línea la cantidad de números diferentes en el intervalo $(i,j)$ de la secuencia.

Sample test(s)