Count Unique Elements in Subarrays

You are given an array (a) of (n) integers and (m) queries. Each query is represented by two integers (l) and (r) (1-indexed), which define a subarray (a[l \ldots r]). For each query, determine the number of distinct elements in the specified subarray.

The input is read from standard input and the output should be printed to standard output. Make sure that your solution reads from stdin and writes to stdout.

inputFormat

The first line contains two integers (n) and (m): 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 next (m) lines contains two integers (l) and (r) (with (1 \leq l \leq r \leq n)) which represent a query.

outputFormat

For each query, output a single integer on a new line: the number of unique elements in the subarray (a[l \ldots r]).## sample

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

3
4