== 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$ aflata intre pozitiile $i$ si $j$? $(i ≤ 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 mai mici sau egale decat $100 000$
* Pentru $50%$ din teste $N ≤ 1000$
* Pentru $50%$ din teste elementele secventei $A$ sunt numere naturale mai mici sau egale decat $30$
h2. Exemplu
table(example). |_. inversari.in |_. inversari.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5
4 2 5 3 1
1 5
2 4
3 5
1 3
2 3
| 7
1
3
1
0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="inversari") ==
