Distinct Elements in Subarray

Given an array of integers and multiple queries, for each query, determine the number of distinct elements in the subarray defined by the given indices (1-indexed).

For a query with two integers \(L\) and \(R\), you must compute the number of distinct integer values in the subarray \([a_L, a_{L+1}, \dots, a_R]\). In mathematical notation, the answer for a query is given by:

$$\text{answer} = \left|\{a_i : L \leq i \leq R\}\right|.$$

Your task is to process each query and output the result on a separate line.

inputFormat

The input is given from standard input (stdin) in the following format:

1. The first line contains an integer (n), the number of elements in the array.
2. The second line contains (n) space-separated integers representing the array elements.
3. The third line contains an integer (q), the number of queries.
4. Each of the following (q) lines contains two integers (L) and (R) (1-indexed) representing a query.

outputFormat

For each query, output a single integer representing the number of distinct elements in the subarray from index (L) to (R). Each result should be printed on a new line to standard output (stdout).## sample

5
1 2 1 3 2
1
1 3

2