SP3267 DQUERY - D-query

Given a sequence of n numbers $a_{1} , a_{2}, \cdots, a_{n} $ and a number of d-queries. A d-query is a pair $(i, j)$ ($1 \le i \le j \le n$). For each d-query $(i, j)$, you have to return the number of distinct elements in the subsequence $a_{i} , a _{i+1} , \cdots, a_{j} $ .

- Line 1: $n$ ($1 \le n \le 30000$). - Line 2: $n$ numbers $a_{1} , a _{2} , \cdots, a _{n} $ ($1 \le a_{i} \le 10 ^{6}$ ). - Line 3: $q$ ($1 ≤ q ≤ 200000$), the number of d-queries. - In the next q lines, each line contains 2 numbers i, j representing a d-query ($1 ≤ i ≤ j ≤ n$).

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