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

 
bq. _Am pus cărămidă peste cărămidă_
_Până am ajuns sus pe piramidă_
 
Mulţi dintre noi rămânem înmărmuriţi de măreţia singurei din cele _Şapte minuni ale lumii antice_ care s-a păstrat peste vreme. Puţini suntem însă cei care ştiu cum au fost construite, de fapt, piramidele. Ultimele date istorice ne arată că pe vremea lui faraon se trăia într-o sărăcie lucie, rata şomajului fiind de 100%.
Întrebarea rămâne: de unde a avut totuşi faraon bani pentru a construi piramidele? De la cămătari, desigur (cei care făceau contrabandă cu probleme furate).
 
Zis şi făcut, faraon a împrumutat bani de la aceştia şi a construit cele mai înalte şi mai frumoase piramide din întreaga lume la acele timpuri, iar banii rămaşi i-a pierdut la păcănele, la Book of Ra desigur. Problema a urmat însă când a trebuit să înapoieze banii ...
 
Norocul face însă că faraon avea la mână $n$ degete. Lungimile degetelor sale erau distincte două câte două şi formau o $permutare$.
Pe măsură ce deadline-ul se apropia, cămătarii l-au sunat pe faraon şi i-au transmis că dacă nu va înapoia banii vor alege un interval $[l[~i~], r[~i~]]$ al degetelor sale şi, cu fiecare întârziere, vor alege din acesta un deget $p[~i+1~]$ cu proprietatea că $p[~i~] < p[~i+1~] > p[~i+2~]$ pe care îl vor tăia, până ce nu va mai exista un astfel de deget.
 
Speriat, faraon doreşte să afle răspunsul la $q$ întrebări: Dacă ar fi ca cămătarii să aleagă intervalul $[l[~i~], r[~i~]]$, cu câte degete va mai rămâne în acest interval la final?

Se da un n si o permutare de lungime n si operatia A -> daca pi < pi+1 > pi+2, se elimina pi+1. Se cere sa se raspunda q intrebari de tipul:
left right -> daca am aplica operatia A numai pe intervalul [left, right] pana cand nu se mai poate, cu cate elemente am ramane?

h2. Date de intrare

Fişierul de intrare $valearegilor.in$ conţine pe prima linie numerele $n$ şi $q$. Pe următoarea linie se vor găsi lungimile degetelor sub formă de permutare $p[~1~] p[~2~] ... p[~n~]$. Urmează $q$ linii descriind întrebările sub forma $l[~i~] r[~i~]$.

Fişierul de intrare $valearegilor.in$ conţine pe prima linie numerele $n$ si $q$. Pe urmatoarea linie se vor gasi lungimile degetelor sub forma de permutare $p[~1~] p[~2~] ... p[~n~]$. Urmeaza $q$ linii descriind intrebarile sub forma $l[~i~] r[~i~]$.

h2. Date de ieşire

În fişierul de ieşire $valearegilor.out$ veţi afişa răspunsul la cele $q$ întrebări ale lui faraon, câte unul pe linie.

În fişierul de ieşire $valearegilor.out$ veţi afişa raspunsul la cele $q$ intrebari ale lui faraon, cate unul pe linie.

h2. Restricţii
* $1 ≤ n ≤ 100.000$
* $1 ≤ q ≤ 1.000.000$

* $1 ≤ $l[~i~]$ ≤ $r[~i~]$ ≤ n$
* Se va considera că degetele $l[~i~]-1$ şi $r[~i~]+1$ au lungimea $infinit$ în cadrul unei întrebări.

* Se va considera ca degetele $l[~i~]-1$ si $r[~i~]+1$ au lungimea infinit in cadrul unei intrebari.

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

| 15 4
1 2 3 4 5 10 8 6 7 9 14 13 11 12 15
1 5
3 3
10 14
4 15
| 5
1
3
8

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

|
== include(page="template/taskfooter" task_id="valearegilor") ==