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

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.

Poveste şi cerinţă...

h2. Date de intrare

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

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

h2. Date de ieşire

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

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

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 |

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

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

|

h3. Explicaţie
 
...
 

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