問題文

長さ $N$ の配列 $A$ が与えられます。

また、$Q$ 個のクエリが与えられるので、順番に処理してください。
$i$ 個目のクエリでは $L_i, R_i$ が与えられるので、以下の値を求めてください。

• $A_{L_i}, A_{{L_i} + 1}, …, A_{R_i}$ について、最も現れない値の現れる回数

制約

• $1 \leq N, Q \leq 2 \times 10^4$
• $1 \leq A_i \leq 2 \times 10^4 \: (1 \leq i \leq N)$
• $1 \leq L_i \leq R_i \leq N \: (1 \leq i \leq Q)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
A1 A2 ... AN
L1 R1
L2 R2
... ...
LQ RQ

出力

それぞれのクエリに対する答えを改行区切りで出力せよ。

入出力例

5 2
1 2 3 2 3
1 5
2 5

1
2

最初のクエリについて、$1$ が $1$ 回だけ現れているため、$1$ と出力します。
$2$ 番目のクエリについて、$2$ と $3$ のいずれも $2$ 回ずつ現れているため、$2$ と出力します。

9 6
1 3 8 8 9 3 9 1 2
1 5
1 7
1 9
2 7
2 8
3 4

1
1
1
2
1
2