Ferume は私に、$O(n\sqrt{n} \log n)$ より速く解けるかと尋ねました。そして、私は解くことができました！この問題を作成し、退屈な解法で終わらせなかった彼に感謝します。

$S$ を非負整数を含む多重集合とします。$S$ に対して以下の操作を任意の回数（0回でもよい）行うことができます：$S$ 内に $x$ が少なくとも2つ存在するように $x$ を選び、そのうちの1つを削除し、代わりに $(x - 1)$ または $(x + 1)$ を1つ挿入する（ただし、$(x - 1)$ を挿入できるのはそれが非負の場合のみ）。$F(S)$ を、これらの操作によって達成可能な最大の mex とします。ここで $\text{mex}(S)$ とは、$S$ に含まれない最小の非負整数を指します。

長さ $n$ の配列 $a$ と $q$ 個のクエリ $[l, r]$ が与えられます。各クエリについて、$F(\{a_l, a_{l+1}, \dots, a_r\})$ を求めてください。

入力

1行目に2つの整数 $n, q$ ($1 \le n, q \le 5 \cdot 10^5$) が与えられます。これは配列のサイズとクエリの数です。

2行目に配列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$) が与えられます。

続く $q$ 行に、各クエリを表す2つの整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$) が与えられます。

出力

各クエリに対する答えを、入力された順にそれぞれ別の行に出力してください。

入出力例

入力 1

3 3
0 0 2
1 3
2 3
3 3

出力 1

3
1
0

入力 2

3 2
1 2 2
1 2
1 3

出力 2

0
3