HH has a necklace made of various beautiful shells. HH believes that different shells bring good luck, so after every walk, he picks a segment of the necklace and contemplates their meaning. HH keeps collecting new shells, so his necklace is becoming longer and longer. One day, he suddenly raised a question: how many different types of shells are contained in a certain segment? This question is hard to answer... because the necklace is simply too long. Therefore, he has to turn to you, the wise one, to solve this problem.
Input
The first line contains an integer $N$, representing the length of the necklace.
The second line contains $N$ integers, representing the IDs of the shells in the necklace in order (the IDs are integers between $0$ and $1\,000\,000$).
The third line contains an integer $M$, representing the number of queries HH makes.
The next $M$ lines each contain two integers, $L$ and $R$ ($1 \leq L \leq R \leq N$), representing the queried range.
Output
$M$ lines, each containing an integer, representing the answer to the corresponding query.
Examples
Input 1
6 1 2 3 4 3 5 3 1 2 3 5 2 6
Output 1
2 2 4
Subtasks
| Test Case | $N$ | $M$ |
|---|---|---|
| $1$ | $100$ | $100$ |
| $2$ | $1\,000$ | $1\,000$ |
| $3$ | $2\,000$ | $200\,000$ |
| $4$ | $3\,000$ | $200\,000$ |
| $5$ | $30\,000$ | $200\,000$ |
| $6$ | $40\,000$ | $200\,000$ |
| $7 \sim 10$ | $50\,000$ | $200\,000$ |
For $100\%$ of the data, $1 \leq N \leq 50\,000$ and $1 \leq M \leq 200\,000$.