Count Distinct Elements in Subarrays

You are given an array of integers and a series of queries. For each query, you need to calculate the number of distinct elements in the subarray defined by the query.

Each query consists of two integers, \(l\) and \(r\), which represent the 1-based starting and ending indices of the subarray. Your task is to output, for each query, the count of unique elements in the corresponding subarray.

For example, if the array is [1, 2, 1, 3, 2, 3] and the query is (1, 3), then the subarray is [1, 2, 1]. There are 2 distinct elements (1 and 2), so the output should be 2.

inputFormat

The input is read from standard input (stdin).\n\nThe first line contains two integers (n) and (q) denoting the number of elements in the array and the number of queries respectively.\n\nThe second line contains (n) space-separated integers representing the array elements.\n\nEach of the following (q) lines contains two integers (l) and (r) (1-based indices) representing a query for the subarray from index (l) to (r) (inclusive).

outputFormat

For each query, print a single line to standard output (stdout) containing one integer — the number of distinct elements in the specified subarray.## sample

6 3
1 2 1 3 2 3
1 3
2 4
1 6

2
3
3