Distinct Elements in Subarray

You are given an array of n integers and m queries. Each query asks for the number of distinct elements in a subarray of the given array. More precisely, for a query given by indices l and r, you are to compute the number of unique elements in the subarray from index l to r (both inclusive).

You can express the answer to a query mathematically as \( |\{a_i : l \leq i \leq r\}| \), where \(|\cdot|\) denotes the cardinality (number of elements) of the set.

The input must be processed from standard input and the results should be printed to standard output, each on a new line.

inputFormat

The first line contains two integers n and m \( (1 \le n, m \le 10^5) \), representing the number of elements in the array and the number of queries respectively.

The second line contains n integers \(a_1, a_2, \ldots, a_n\) representing the elements of the array.

The following m lines each contain two integers \(l\) and \(r\) \( (1 \le l \le r \le n) \), describing a query for the subarray from index l to r.

outputFormat

For each query, output a single line containing one integer: the number of distinct elements found in the subarray defined by that query.

## sample

5 3
1 2 1 3 2
1 3
2 4
1 5

2
3
3

</p>