408668: GYM103260 H Excluded Min
Description
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} \})$$$.
InputThe 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.
OutputPrint answers to queries in the order they are listed in input on separate lines.
ExamplesInput3 3 0 0 2 1 3 2 3 3 3Output
3 1 0Input
3 2 1 2 2 1 2 1 3Output
0 3