Given a sequence of $n$ numbers $a_1, a_2, ..., a_n$ and a number of d-queries. A d-query is a pair $(i, j)\ (1 ≤ i ≤ j ≤ n)$. 

For each d-query $(i, j)$, you have to return the number of distinct elements in the subsequence $a_i, a_{i+1}, ..., a_j$.

Line 1: $n\ (1 ≤ n ≤ 30,000)$.
Line 2: $n$ numbers $a_1, a_2, ..., a_n\ (1 ≤ a_i ≤ 10^6)$.
Line 3: $q\ (1 ≤ q ≤ 200,000)$, the number of d-queries.
In the next $q$ lines, each line contains $2$ numbers $i, j\ (1\leq i \leq j \leq n)$ representing a d-query.

For each d-query $(i, j)$, print the number of distinct elements in the subsequence $a_i, a_{i+1}, ..., a_j$ in a single line.