Count Unique Elements in a Subarray

You are given an array of n integers and q queries. For each query you are provided with two integers, l and r (using 1-based indexing), describing the endpoints of a subarray. Your task is to count the number of distinct integers in the subarray from index l to r (inclusive).

Formally, for each query you need to compute:

$$answer = \left| \{arr[i] : l \leq i \leq r\} \right|, $$

where \(|S|\) denotes the size of set \(S\).

Input via stdin and output the result for each query to stdout.

inputFormat

The input is read from stdin in the following format:

• The first line contains a single integer n, the number of elements in the array.
• The second line contains n space-separated integers representing the array.
• The third line contains a single integer q, the number of queries.
• The following q lines each contain two space-separated integers l and r (1-based indices) representing a query.

If n is 0, the array is empty.

outputFormat

For each query, output a single integer on a new line representing the number of unique elements in the specified subarray.

## sample

7
1 2 1 3 4 2 3
1
1 4

3

</p>