Ferume m'a demandé si je pouvais résoudre ce problème plus rapidement que $O(n\sqrt{n} \log n)$. Et il s'avère que je peux ! Merci à lui d'avoir créé ce problème et de ne pas l'avoir laissé se contenter d'une solution ennuyeuse.

Soit $S$ un multiensemble contenant des entiers non négatifs. Vous pouvez effectuer l'opération suivante sur $S$ un nombre arbitraire de fois (éventuellement zéro) : choisir $x$ tel qu'il y ait au moins deux occurrences de $x$ dans $S$, supprimer l'une des occurrences, mais insérer à la place une occurrence de $(x - 1)$ ou $(x + 1)$ (vous ne pouvez insérer $(x - 1)$ que si le résultat est non négatif). Soit $F(S)$ le mex maximal que vous pouvez atteindre avec ces opérations. Ici, $\text{mex}(S)$ est le plus petit entier non négatif qui n'est pas présent dans $S$.

On vous donne un tableau $a$ de longueur $n$ et $q$ requêtes $[l; r]$. Pour chaque requête, trouvez $F(\{a_l, a_{l+1}, \dots, a_r\})$.

Entrée

La première ligne contient deux entiers $n, q$ ($1 \le n, q \le 5 \cdot 10^5$) — la taille du tableau et le nombre de requêtes.

La deuxième ligne contient le tableau d'entiers $a_1, a_2, \dots, a_n$ lui-même ($0 \le a_i \le 5 \cdot 10^5$).

Les $q$ lignes suivantes contiennent deux entiers $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — la $i$-ième requête.

Sortie

Affichez les réponses aux requêtes dans l'ordre où elles sont listées dans l'entrée, sur des lignes séparées.

Exemples

Entrée 1

3 3
0 0 2
1 3
2 3
3 3

Sortie 1

3
1
0

Entrée 2

3 2
1 2 2
1 2
1 3

Sortie 2

0
3