21089번 - 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 $mex(S)$ you can achieve with these operations. Here $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 $a_{1}, a_{2}, \ldots, a_{n}$ itself ($0 \le a_{i} \le 5 \cdot 10^{5}$).

Next $q$ lines contain queries $l_{i}$ $r_{i}$ ($1 \le l_{i} \le r_{i} \le n$).

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