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 :)

* Cele $M$ query-uri sunt sortate descrescator dupa $b - a$
* Atentie la limita de memorie

h2. Exemplu

3
|

h3. Explicaţie
 
...
 

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