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

Poveste şi cerinţă...

Pe langa vechile lui pasiuni artistice, Zuru are acum o pasiune pentru inversari. Profesorul sau de filosofie ii pune la dipozitie o secventa $A$ care contine $N$ numere naturale. Apoi ii pune $M$ intrebari de forma: cate inversari contine subsecventa din sirul $A$ situata intre pozitiile $i$ si $j$? ($i&le;j). Pentru ca este un perfectionist, Zuru va cere ajutorul pentru a raspunde la fiecare din intrebarile puse de profesor. Zuru s-a gandit ca ar fi bine sa va spuna si cum defineste el o inversare. In viziunea sa o inversare este o pereche de indici $(p, q)$ cu $p < q$ astfel incat $A{~p~} > A{~q~}$.

h2. Date de intrare

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

Fişierul de intrare $inversari.in$ contine pe prima linie $N$ si $M$, separate de un singur spatiu, avand semnificatie din enunt. Urmatoarea linie contine cele $N$ numere naturale ale secventei $A$, separate prin cate un singur spatiu. Pe urmatoarele $M$ linii se afla intrebarile puse de profesor, pe fiecare linie aflandu-se doua numere separate printr-un spatiu, $i$ si $j$ ($i≤j$), capetele subsecventei.

h2. Date de ieşire

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

În fişierul de ieşire $inversari.out$ se afla $M$ linii, pe fiecare linie veti afisa raspunsul la intrebarile profesorului, in ordinea in care acestea apar in fisierul de intrare.

h2. Restricţii

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

* $1 ≤ N ≤ 5000$
* $1 ≤ M ≤ 100 000$
* Elementele secventei $A$ sunt numere naturale intregi pe $32$ biti

h2. Exemplu