h2. Date de intrare

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.

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

* $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$

* Elementele secventei $A$ sunt numere naturale intregi pe $32$ biti

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

| 5 5
4 2 5 3 1
1 5
2 4
3 5
1 3
2 3
| 7
1
3
1
0

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

|

h3. Explicaţie
 
...
 

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

4846