Distinct values in a range

A sequence $A_1, A_2, \dots, A_N$ of length $N$ is given. Write a program that answers $M$ queries on this sequence.

• i j: report how many distinct numbers appear among $A_i, A_{i+1}, \dots, A_j$.

A value that appears several times inside the range counts once.

The first line contains the size of the sequence, $N$. ($1 \le N \le 100{,}000$)

The second line contains $A_1, A_2, \dots, A_N$, separated by spaces. ($1 \le A_i \le 1{,}000{,}000$)

The third line contains the number of queries, $M$. ($1 \le M \le 100{,}000$)

Each of the next $M$ lines holds one query as two integers $i$ and $j$. ($1 \le i \le j \le N$)

For each query, print the number of distinct values in the range $[i, j]$ on its own line, in the order the queries are given.