Distinct Elements Query

You are given an array (A) consisting of (N) integers and (Q) queries. Each query is described by two integers (l) and (r) (1-indexed), and your task is to determine the number of distinct elements present in the subarray (A[l\ldots r]).

For example, if (A = [1, 2, 1, 3, 2]) and the query is ((1, 3)), the subarray is ([1,2,1]) and the number of distinct elements is (2) (i.e. (1) and (2)).

The solution should read input from standard input (stdin) and produce output to standard output (stdout).

inputFormat

The first line contains two space-separated integers (N) and (Q), denoting the number of elements in the array and the number of queries, respectively. The second line contains (N) space-separated integers representing the array (A). Each of the following (Q) lines contains two space-separated integers (l) and (r), representing a query.

outputFormat

For each query, output a single line containing the number of distinct elements in the subarray (A[l\ldots r]).## sample

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

2
3
3