Fişierul intrare/ieşire:verkhoyansk.in, verkhoyansk.outSursăTuymaada 2019
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu •alexpetrescu
Timp execuţie pe test1.25 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Verkhoyansk

Marcel a planuit o excursie in Muntii Verkhoyansk, un lant muntos de 1200 de kilometri in Republica Sakha. Peisajul poate fi vazut ca un vector de N numere naturale, cu valori intre 1 si N, reprezentand inaltimile varfurilor muntoase ale lantului.

Marcel are Q prieteni. Prietenul i va vizita toate varfurile cu indicii intre L[i] si R[i] inclusiv. Marcel vrea sa stie, pentru fiecare dintre ei, care este cea mai mica inaltime a unui varf, numar natural pozitiv, pe care fiecare prieten nu o va vizita. El trebuie sa stie asta pentru a-si planifica in mod optim urmatoarea lui excursie.

De exemplu, daca un prieten viziteaza varfurile cu inaltimile 3 2 5 1 1 6 3 5, cea mai mica inaltime naturala pozitiva a unui varf pe care el nu a vizitat-o este 4.

Input

Pe prima linie a fisierului de intrare verkhoyansk.in se vor afla numerele N si Q. Pe a doua linie se afla N numere naturale cu valori intre 1 si N, reprezentand inaltimile varfurilor muntoase. Urmatoarele Q linii contin fiecare cate 2 numere, L[i] si R[i], cu 0 ≤ L[i] ≤ R[i] ≤ N - 1.

Output

In fisierul de iesire verkhoyansk.out se vor afla Q linii. Pe linia i se afla cea mai mica inaltime, numar natural pozitiv, pe care prietenul cu numarul i nu o va vizita.

Restrictii si precizari

  • 1 ≤ N ≤ 300.000, 1 ≤ Q ≤ 600.000
  • Pentru 8 puncte, N ≤ 1.000, Q ≤ 10.000
  • Pentru alte 8 puncte, N ≤ 100.000, Q ≤ 200.000 si toate inaltimile sunt mai mici sau egale cu 50
  • Pentru alte 56 puncte, N ≤ 100.000, Q ≤ 200.000
  • Distributia scorului e diferita de cea din timpul concursului oficial.
  • Vectorul inaltimilor incepe cu pozitia 0.
  • Putem observa ca Marcel are foarte multi prieteni.
  • 0 nu este nici pozitiv si nici negativ.

Exemplu

verkhoyansk.inverkhoyansk.out
14 16
3 4 3 2 5 1 6 7 2 1 6 2 4 3
0 4
0 5
9 13
9 12
3 12
2 12
2 11
1 11
3 13
5 13
8 13
0 7
0 8
6 8
6 9
6 10
1
6
5
3
3
8
4
8
8
5
5
8
8
1
3
3
16 32
8 7 6 5 2 1 8 7 1 2 3 4 5 6 3 4
1 14
0 2
2 5
1 13
12 14
1 9
5 14
1 15
5 10
2 2
4 10
5 11
5 13
0 10
0 15
1 13
7 15
3 6
12 14
3 5
14 14
2 10
0 12
2 15
0 0
4 8
0 12
0 7
6 15
3 5
1 14
2 14
9
1
3
9
1
3
9
9
4
1
4
5
9
4
9
9
8
3
1
3
1
4
9
9
1
3
9
3
9
3
9
9

Tutorial

Puteti vedea solutia problemei la editorial

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?