Count Distinct Elements in Subarrays

You are given an array of N integers and Q queries. For each query, you should find the number of distinct elements in the subarray from index L to R (both inclusive).

The answer for a single query can be mathematically represented as:

$$\text{distinct}(L, R) = \left| \{ a_i : L \le i \le R \} \right|$$

Input will be provided via standard input and the output should be written to standard output. Each answer should be printed on a new line.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers N and Q, representing the number of elements in the array and the number of queries respectively.
2. The second line contains N space-separated integers which are the elements of the array.
3. The next Q lines each contain two integers L and R, defining a query to count distinct elements in the subarray array[L...R].

outputFormat

For each query, output a single integer representing the number of distinct elements in the specified subarray. Each result should be printed on a new line.

## sample

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

2
3
3

</p>