Distinct Elements in Subarrays

You are given an array of n integers and q queries. Each query consists of two integers l and r which represent the indices of a subarray (using 1-based indexing). Your task is to determine the number of distinct elements in the subarray defined by the range \(l\) to \(r\).

Example:

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

</p>

In the sample, the distinct numbers in the ranges [1,3], [2,4] and [1,5] are computed respectively. Use efficient methods if possible, but note that constraints allow for simpler solutions.

inputFormat

The first line contains two integers \(n\) and \(q\), the number of elements in the array and the number of queries, respectively. The second line contains \(n\) integers representing the array. Each of the next \(q\) lines contains two integers \(l\) and \(r\) (1-based indexing), representing the range of the query.

outputFormat

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

## sample

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

2
3
3

</p>