Distinct Elements in Subarray

You are given an array \(B\) of \(n\) integers and \(q\) queries. Each query is represented by two integers \(L\) and \(R\) (1-indexed). For each query, your task is to calculate the number of distinct elements in the subarray \(B[L \ldots R]\).

Input Constraints:

• \(1 \leq n \leq 10^5\)
• \(1 \leq B_i \leq 10^9\)
• \(1 \leq q \leq 10^5\)
• \(1 \leq L \leq R \leq n\)

Example:

Input:
7
5 3 5 2 2 3 1
3
1 3
1 7
4 6
Output:
2
4
2

</p>

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array \(B\).

The second line contains \(n\) space-separated integers representing the elements of \(B\).

The third line contains a single integer \(q\) representing the number of queries.

Each of the next \(q\) lines contains two space-separated integers \(L\) and \(R\) representing a query.

outputFormat

For each query, output a single integer, the number of distinct elements in the subarray \(B[L \ldots R]\). Print the results on separate lines.

## sample

7
5 3 5 2 2 3 1
3
1 3
1 7
4 6

2
4
2

</p>