Ferume 問我是否能比 $O(n\sqrt{n} \log n)$ 更快地解決這個問題。結果我做到了！感謝他創造了這個問題，沒有讓它淪為一個無聊的解法。

令 $S$ 為一個包含非負整數的多重集。你可以對 $S$ 進行任意次（包含零次）以下操作：選擇一個 $x$，使得 $S$ 中至少有兩個 $x$，刪除其中一個 $x$，並插入一個 $(x - 1)$ 或 $(x + 1)$（只有在 $(x - 1)$ 為非負整數時才能插入 $(x - 1)$）。令 $F(S)$ 為透過這些操作所能達到的最大 mex 值。其中 $\text{mex}(S)$ 是指不在 $S$ 中的最小非負整數。

給定一個長度為 $n$ 的陣列 $a$ 以及 $q$ 個查詢 $[l; r]$。對於每個查詢，請找出 $F(\{a_l, a_{l+1}, \dots, a_r\})$。

輸入格式

第一行包含兩個整數 $n, q$ ($1 \le n, q \le 5 \cdot 10^5$)，分別代表陣列大小與查詢數量。 第二行包含陣列中的整數 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$)。 接下來 $q$ 行，每行包含兩個整數 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)，代表第 $i$ 個查詢。

輸出格式

依序輸出每個查詢的答案，每個答案佔一行。

範例

範例輸入 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