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

Есеп C. Макс MEX

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

4 seconds

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

512 megabytes

Профессор Айдос мектепте информатике пәнінен сабақ береді. Бүгін ол 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$-ші тапсырыс үшін $l_i$, $l_i + 1$, $\dots$, $r_i$ карталарының арасында MEX есептеу керек. Темірлан карталарды өз қалауынша аудара алады және әр тапсырыс үшін ол максималды MEX алғысы келеді. Темірлан ұйықтауын жалғасытырып, сенен осы мәселені шешіп беруіңді өтінді.

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

Бірінші жолда бір бүтін сан $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$) беріледі.

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

Әр тапсырыс үшін бір бүтін санды шығарыңыз — алуға болатын максималды МЕX.

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

Есеп $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 )