Sarac sau Rege

Sarac Sau Rege

== include(page="template/taskheader" task_id="saracsaurege") ==

Poveste şi cerinţă...

Se da un sir cu $N$ elemente si $M$ query-uri. Pentru fiecare query se dau $2$ valori $a$ si $b$, iar Zeul Valorii trebuie sa decida daca secventa este Sarac sau Rege. Pentru asta, voi trebuie sa afisati valoarea maxima din acea secventa.

h2. Date de intrare

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

Fişierul de intrare $saracsaurege.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$. Pe linia $2$ vor fi $N$ numere reprezentand sirul dat. Urmatoarele $M$ linii vor contine cate $2$ numere $a$ si $b$, reprezentand query-urile sortate dupa $b - a$.

h2. Date de ieşire

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

Fişierul de ieşire $saracsaurege.out$ va contine $M$ valori reprezentand raspunsul la cele $M$ query-uri.

h2. Restricţii

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

* $1 ≤ N ≤ 50.000$
* $1 ≤ M ≤ 1.000.000$
* *Cele $M$ query-uri sunt sortate descrescator dupa $b - a$.*
* Atentie la limita de memorie!
* Incercati sa rezolvati problema cu O(n * log n + m) timp si O(n) memorie :)

h2. Exemplu
table(example). |_. saracsaurege.in |_. saracsaurege.out |

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

|5 3
7 6 9 3 8
2 5
1 2
4 4
|9
7
3

|

h3. Explicaţie
 
...
 

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