Verkhoyansk

verkhoyansk

== include(page="template/taskheader" task_id="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.

Poveste şi cerinţă...

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.

h2. Date de intrare

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$.

Fişierul de intrare $verkhoyansk.in$ ...

h2. Input

h2. Date de ieşire

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$.

În fişierul de ieşire $verkhoyansk.out$ ...

h2. Output

h2. Restricţii

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.
 
h2. 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.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. verkhoyansk.in |_. verkhoyansk.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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Tutorial

h3. Explicaţie

Puteti vedea solutia problemei la 'editorial':verkhoyansk/solutie_romana

...

== include(page="template/taskfooter" task_id="verkhoyansk") ==