cuburi2

Cuburi2

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

Poveste şi cerinţă...

Laura si Robert se joaca cu cuburile. Robert a construit $N$ turnuri in linie dreapta si stie inaltimea fiecaruia. Pentru a muta un cub dintr-un turn in turnul vecin costa o unitate de timp. Acum, el ii pune $M$ intrebari Laurei in felul urmator: _"Care este timpul minim necesar pentru a muta toate cuburile din intervalul $x y$ intr-un singur turn deja existent?"_ Desigur, pe el il intereseaza si care va fi turnul destinatie ales in cazul unei astfel de intrebari. Laura ar putea raspunde cu usurinta la aceste intrebari folosindu-si intuitia feminina, dar s-a decis sa o pastreze pentru alte ocazii. Asadar, va trebui ca voi sa raspundeti la intrebarile lui Robert.

h2. Date de intrare

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

Pe prima linie a fisierului de intrare $cuburi2.in$ se afla numerele $N$ si $M$. Pe urmatoarea linie se afla $N$ numere, semnificand inaltimea turnurilor. Urmatoarele $M$ linii contin cate doua numere $x y$, fiecare pereche reprezentand o intrebare pusa de Robert.

h2. Date de ieşire

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

In fisierul de iesire $cuburi2.out$ se vor afla $M$ linii, pe fiecare linie aflandu-se raspunsul la cate o intrebare pusa de Robert. Raspunsurile vor fi afisate sub forma $P Cost$, unde $P$ reprezinta pozitia turnului destinatie pentru intrebarea respectiva, iar $Cost$ timpul minim necesar pentru a muta toate cuburile intr-un singur turn.

h2. Restricţii

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

* $1 ≤ N ≤ 250 000$
* $1 ≤ M ≤ 250 000$
* Pentru

h2. Exemplu