Laiko ribojimas: 2s

Atminties ribojimas: 128MB

Duomenų failas: mex.in

Rezultatų failas: mex.out

Jei norite pateikti savo sprendimą - prisijunkite.

MEX užklausos

Baigtinės aibės MEX yra mažiausias natūralusis skaičius, kurio nėra toje aibėje.

Jums yra duotas ilgio n natūraliųjų skaičių sąrašas, ir q užklausų (l_i,r_i). Kiekvienai užklausai raskite sąrašo intervalo nuo l_i iki r_i (imtinai) MEX.

Pradiniai duomenys

Pirmoje eilutėje yra du skaičiai: n ir q (1\\leqn,q\\leq5\\times10^5). Antroje eilutėje yra n skaičių a_i - sąrašo elementai (0\\leqa_i\\leq5\\times10^5). Sekančiose q eilučių yra po du skaičius l_i ir r_i - i-tosios užklausos intervalas (1\\leql_i\\leqr_i\\leqn).

Rezultatai

Išspausdinkite q skaičių - kiekvienos užklausos sąrašo intervalo MEX.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
10 7
2 0 1 3 0 0 2 4 7 1
1 2
5 6
5 10
1 3
1 5
6 6
7 8
 
1
1
3
3
4
1
0