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.