408668: GYM103260 H Excluded Min

Ferume asked me if I can solve this faster than $$$O(n \sqrt{n} \log n)$$$. And it turns out I can! Thanks to him for creating this problem and not letting it live with boring solution.

Let $$$S$$$ be a multiset containing non-negative integers. You can do the following operation on $$$S$$$ arbitrary number of times (possibly zero): choose $$$x$$$ such that there are at least two occurrences of $$$x$$$ in $$$S$$$, delete one of the occurrences but insert one occurrence of $$$(x-1)$$$ or $$$(x+1)$$$ instead (you can insert $$$(x-1)$$$ only if it is non-negative). Let $$$F(S)$$$ be the maximum $$$\mathrm{mex}$$$ you can achieve with these operations. Here $$$\mathrm{mex}(S)$$$ is the minimal non-negative integer which is not present in $$$S$$$.

You are given an array $$$a$$$ of length $$$n$$$ and $$$q$$$ queries $$$[l;r]$$$. For each query, find $$$F(\{ a_{l}, a_{l + 1}, \ldots, a_{r} \})$$$.

The first line contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^{5}$$$) — the size of array and the number of queries.

The second line contains the array of integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ itself ($$$0 \le a_{i} \le 5 \cdot 10^{5}$$$).

Next $$$q$$$ lines contain two integers $$$l_{i}$$$ $$$r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le n$$$) — $$$i$$$-th query.

Print answers to queries in the order they are listed in input on separate lines.

3 3
0 0 2
1 3
2 3
3 3

3
1
0

3 2
1 2 2
1 2
1 3

0
3