제외 최소값

Ferume이 이 문제를 $O(n \sqrt{n} \log n)$보다 빠르게 풀 수 있냐고 물었다. 그리고 실제로 풀 수 있었다! 이 문제를 만들어 주고, 지루한 풀이로 남지 않게 해 준 그에게 감사한다.

$S$를 음이 아닌 정수들의 다중집합이라고 하자. $S$에 대해 다음 연산을 0번을 포함해 임의의 횟수만큼 할 수 있다. $S$에 두 개 이상 들어 있는 $x$를 하나 고르고, 그 중 한 개를 삭제한 뒤 대신 $x-1$ 또는 $x+1$을 삽입한다. $x-1$은 음이 아닐 때에만 삽입할 수 있다. $F(S)$를 이 연산들로 얻을 수 있는 최대 $mex(S)$라고 하자. 여기서 $mex(S)$는 $S$에 없는 가장 작은 음이 아닌 정수이다.

길이가 $n$인 배열 $a$와 $q$개의 질의 $[l;r]$이 주어진다. 각 질의에 대해 $F(\{ a_l, a_{l+1}, \ldots, a_r \})$를 구하라.

첫째 줄에 배열의 크기 $n$과 질의의 개수 $q$가 주어진다 ($1 \le n, q \le 5 \cdot 10^5$). 둘째 줄에 배열 $a_1, a_2, \ldots, 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$).

각 질의의 답을 입력된 순서대로 한 줄에 하나씩 출력한다.