L. Минимальное отсутствующее

Для каждого отрезка нужно найти минимальное неотрицательное число, которого на нём нет.

Каркас - алгоритм Мо из классной задачи L: те же счётчики cnt[v], те же четыре сдвига указателей. Вопрос в том, как быстро отвечать.

В первой строке - число $n$ ($1 \le n \le 10^5$).

Во второй строке - $n$ чисел $a_i$ ($0 \le a_i \le n$).

В третьей строке - число запросов $q$ ($1 \le q \le 10^5$).

В следующих $q$ строках - пары $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите минимальное неотрицательное число, отсутствующее на отрезке.