## CBOJ 2022 Welcome Contest Problem 3 - Suspicious Cells

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

For all subtasks,

\(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}\)

##### Subtask 1 [50%]

\(1 \le N, Q \le 10^{2}\)

##### Subtask 3 [50%]

No additional constraints.

#### 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.

## Comments