Distinct Elements in Subarrays

You are given an array of integers and a series of queries. Each query consists of two integers \(l\) and \(r\), representing the start and end indices (1-indexed) of a subarray. Your task is to determine the number of distinct elements in the subarray defined by \(l\) and \(r\).

Example:

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

</p>

In the above example, the first query asks for the number of distinct elements in the entire array, which is 4, while the second query asks for the number in the subarray from index 2 to 4, which is 2.

inputFormat

The first line of input contains an integer \(n\) — the number of elements in the array.

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

The third line contains an integer \(q\) — the number of queries.

Each of the following \(q\) lines contains two space-separated integers \(l\) and \(r\) (1-indexed) representing the starting and ending indices of a query.

outputFormat

For each query, output a single line containing the number of distinct integers in the subarray from index \(l\) to \(r\) (inclusive).

## sample

5
4 1 2 2 3
2
1 5
2 4

4
2

</p>