== include(page="template/taskheader" task_id="valearegilor") ==
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

n
p1 p2 ... pn
q
l1 r1
l2 r1
....

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

r1
r2
r3
...

Î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 ≤ 100000$
* $1 ≤ q ≤ 1000000$

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

h2. Exemplu

| This is another
  text written on
  multiple lines.

|
 
h3. Explicaţie
 
...

|

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

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