P1972 [SDOI2009] HH's Necklace

HH has a necklace made of various beautiful shells. HH believes different shells bring good luck, so after each walk, he randomly picks a segment of shells and thinks about the meaning they convey. HH keeps collecting new shells, so his necklace becomes longer and longer. One day, he suddenly asked: in a given segment of shells, how many different types of shells are there? This is hard to answer because the necklace is very long. So he turns to you for help to solve this problem.

One line with a positive integer $n$, the length of the necklace. The second line contains $n$ positive integers $a_i$, where $a_i$ denotes the type of the $i$-th shell in the necklace. The third line contains an integer $m$, the number of queries by HH. Then $m$ lines follow, each containing two integers $l, r$, denoting the query interval.

Output $m$ lines, each with a single integer, in order, representing the answer to the corresponding query.

Constraints For $20\%$ of the testdata, $1 \le n, m \leq 5000$. For $40\%$ of the testdata, $1 \le n, m \leq 10^5$. For $60\%$ of the testdata, $1 \le n, m \leq 5\times 10^5$. For $100\%$ of the testdata, $1 \le n, m, a_i \leq 10^6$, $1 \le l \le r \le n$. This problem may require fast input. For the largest testdata, the input size is about 20 MB. Translated by ChatGPT 5