== 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?

Poveste şi cerinţă...

h2. Date de intrare

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

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

h2. Date de ieşire

r1
r2
r3
...

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

h2. Restricţii

* $1 ≤ n ≤ 100000$
* $1 ≤ q ≤ 1000000$

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

h2. Exemplu