4-й этап Республиканской олимпиады по информатике 2022-2023, 1-й тур

Задача C. Макс MEX

Ограничение по времени:

4 секунды

Ограничение по памяти:

512 мегабайт

Профессор Айдос ведет лекции по информатике в старшей школе. Сегодня он объяснил концепт MEX-а. Напомним, что MEX — это минимальное неотрицательное целое число, которое не представлено в множестве. Примеры:

• для множества $[0,0,1,0,2]$ MEX равен $3$, потому что числа $0$, $1$ и $2$ представлены в массиве, а $3$ является минимальным неотрицательным целым числом, не представленным в множестве;
• для множества $[1,2,3,4]$ MEX равен $0$, потому что $0$ является минимальным неотрицательным целым числом, не представленным в множестве;
• для множества $[0,1,4,3]$ MEX равен $2$, потому что $2$ является минимальным неотрицательным целым числом, не представленным в множестве.

Как талантливый студент, Темирлан решил поспать во время лекции и заметивший это Айдос решил проучить своего талантливого но ленивого студента следующей домашней работой: Он дал Темирлану колоду с $n$ картами. У $i$-карты на лицевой строне написано число $a_i$, а в обратной $b_i$. И дал Темирлану задание в виде $q$ отрезков и для $i$-го отрезка нужно посчитать MEX среди карт $l_i$, $l_i + 1$, $\dots$, $r_i$. Темирлан может переворачивать карты как он хочет и нужно независимо для каждого отрезка найти максимальный МЕХ чисел лицевой стороны. Темирлан решил поспать и попросил вас решить данную задачу за него.

Формат входного файла

В первой строке входных данных задано единственное целое число $n$ ($1 <= n <= 2 \cdot 10^5$) — размер колоды. Во второй строке входных данных задано $n$ целых чисел $a_1$, $a_2$, $\dots$, $a_n$ ($0 <= a_i <= n$) — лица карт. В третьей строке входных данных задано $n$ целых чисел $b_1$, $b_2$, $\dots$, $b_n$ ($0 <= b_i <= n$) — другая сторона карт. В четвертой строке входных данных задано единственное целое число $q$ ($1 <= q <= 2 \cdot 10^5$) — количество отрезков. Затем следуют $q$ строк, в каждой из которой задано два целых числа $l_i$ и $r_i$ ($1 <= l_i <= r_i <= n$).

Формат выходного файла

Для каждого отрезка выведите одно целое число — максимальный МЕХ который можно получить.

Система оценки

Данная задача содержит $7$ подзадач.

Примеры:

Вход

3
1 2 2
1 0 3
3
1 2
1 1
1 3

Ответ

2
0
3

Вход

8
2 1 2 4 0 2 0 0
3 1 0 5 2 5 2 2
13
3 7
2 4
4 8
4 8
1 7
1 7
3 6
4 7
4 5
2 6
4 8
3 5
2 8

Ответ

1
2
1
1
6
6
1
1
1
3
1
1
3

Замечание

В первом примере: Первый запрос $l_1 = 1, r_1 = 2$. Перевернем карты $1$ и $2$, тогда с лицевой стороны видно чисел $1$ и $0$, их MEX равен $2$. Второй запрос $l_2 = 1, r_2 = 1$. С обеих сторон написано число $1$, а MEX $[1]$ равен $0$. Третий запрос $l_3 = 1, r_3 = 3$. Перевернем карты $1$ и $2$, тогда с лицевой стороны видно чисел $1$,$0$ и $2$, их MEX равен $3$. ( Dinmukhamed Tursynbay )