| Fişierul intrare/ieşire: | inversari.in, inversari.out | Sursă | Algoritmiada 2010, Runda Finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Inversari
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 Ap > Aq.
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.
Date de ieşire
Î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.
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
Exemplu
| 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 |
