Unique Values in Array Subsegments

You are given an array of n integers and q queries. Each query is represented by two indices l and r. Your task is to compute for each query the number of unique values in the subsegment of the array from index l to r (both inclusive).

In mathematical notation, for an array (a = [a_1, a_2, \dots, a_n]) and a query ((l, r)), you need to calculate [ f(l, r) = \left| { a_i : l \leq i \leq r } \right| ] where (|\cdot|) denotes the cardinality of the set. Ensure that your solution reads from standard input and writes to standard output.

inputFormat

Input is read from stdin. The first line contains two integers n and q, where n is the length of the array and q is the number of queries. The second line contains n integers representing the array. The following q lines each contain two integers l and r, representing a query that asks for the number of unique elements in the subsegment of the array from index l to index r (inclusive).

outputFormat

For each query, output the number of unique values in the corresponding subsegment on a new line, writing the results to stdout.## sample

5 1
1 2 1 3 2
1 3

2