## CBOJ 2022 Welcome Contest Problem 3 - Suspicious Cells

Points: 5
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Today for biology class, Bob and his class have a lab!

For this lab, each person is given $$N$$ cells in a line, the $$i$$-th of which having a positive integer $$A_{i}$$ written on it denoting the species of cell. They are then given their assignment, which is a list of $$Q$$ questions in the following form:

Given two integers $$L$$ and $$R$$ report the number of distinct species starting at the $$L$$-th cell and ending at the $$R$$-th cell (i.e., the number of distinct values in $$[A_{L}, A_{L + 1}, ..., A_{R - 1}, A_{R}]$$).

Being a biology student, Bob hasn't a clue how to solve it! Desperately, Bob comes to you for help. Can you help him?

It is recommended that contestants using Python choose the PyPy interpreter when submitting.

#### Input Specification

The first line will contain a positive integer $$N$$, denoting the amount of cells Bob is given.

The second line will contain $$N$$ space separated positive integers, the $$i$$-th of which represents $$A_{i}$$, the species of the cell.

The third line will contain a positive intger $$Q$$, denoting the amount of questions on Bob's assignment.

The next $$Q$$ lines will each contain two space separated integers, $$L_{i}$$ and $$R_{i}$$, denoting the indices range of the aforementioned query.

#### Output Specification

Output $$Q$$ lines, the $$i$$-th of which is the answer to the $$i$$-th query.

#### Input Constraints

$$1 \le N, Q \le 5 \times 10^{3}$$

$$1 \le L_{i} \le R_{i} \le N$$

$$1 \le A_{i} \le 10^{2}$$

$$1 \le N, Q \le 10^{2}$$

#### Sample Input

5
1 5 4 4 1
5
1 2
3 4
1 5
3 3
4 4

#### Sample Output

2
1
3
1
1

#### Explanation for Sample Output

From the input, $$A=[1, 5, 4, 4, 1]$$.

For the first query, the described subarray is $$[A_{1}, A_{2}]=[1, 5]$$ (note 1-indexing). Since $$1 \ne 5$$, there are $$2$$ distinct species in this.

For the second query, the described subarray is $$[A_{3}, A_{4}]=[4,4]$$. Since $$4=4$$, there is only $$1$$ distinct species in this.

For the third query, the described subarray is $$[A_{1}, A_{2}, A_{3}, A_{4}, A_{5}]=[1,5,4,4,1]$$ (the entire array). Since there are two $$1$$s, one $$5$$, and two $$4$$s, there are $$3$$ distinct species.

For the fourth query, the described subarray is $$[A_{3}]=[4]$$. Since there is only $$1$$ value, there is exactly $$1$$ distinct species.

Finally, For the fifth query, the described subarray is $$[A_{4}]=[4]$$. Since, like the fourth query, there is only $$1$$ value, there is exactly $$1$$ distinct species.