D - Intervalos

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

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)

Input
5 1 1 2 1 3 3 1 5 2 4 3 5
Output
3 2 3