Count Distinct Elements in Subarray

You are given an array of N integers and Q queries. Each query is described by two integers, L and R (1-indexed), which represent the starting and ending indices of a subarray. For each query, you need to calculate the number of distinct elements in the subarray.

For a query with indices L and R, the subarray is arr[L-1...R-1]. The answer for that query is the size of the set formed by the elements in the subarray.

The task is to process all queries and output the answers for each query in the order they are given.

Formula: For a given query, the answer is \[ answer = \left| \{ arr[i] : L \leq i \leq R \} \right| \]

inputFormat

The first line of input contains two integers N and Q, representing the number of elements in the array and the number of queries, respectively.

The second line contains N space-separated integers, representing the elements of the array.

Each of the next Q lines contains two integers L and R (1-indexed) representing a query.

outputFormat

Output a single line containing Q integers. Each integer is the number of distinct elements in the subarray defined by the corresponding query. The answers should be printed in the order of the queries, separated by a space.

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

2 3 3