Segment Uniqueness Query

You are given a sequence of n segments represented by integers, and q queries. Each query is defined by two integers l and r which represent the inclusive indices of a subarray. For every query, your task is to determine the number of unique segments in the specified subarray.

More formally, if the sequence is denoted as \(a_1, a_2, \ldots, a_n\) and a query is given by the interval \([l, r]\), you need to compute:

[ \text{answer} = \left|{ a_i \mid l \leq i \leq r }\right| ]

Input is provided via standard input and you should output the result to standard output. All outputs for the queries should be printed on one line, separated by spaces.

inputFormat

The first line contains two integers n and q, the number of segments and the number of queries respectively.

The second line contains n integers representing the segments.

The following q lines each contain two integers l and r indicating the range (inclusive) of a query.

outputFormat

Print a single line containing q integers. The i-th integer corresponds to the number of unique segments in the subarray specified by the i-th query. The integers should be separated by a single space.

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

2 3 3