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

Poveste şi cerinţă...

Fiindca ar fi fost prea usor sa primiti doar 7 probleme in concurs, comisia s-a gandit sa va dea in cadou si o permutare. Dar pentru ca traim in zilele noastre, se doreste, din punct de vedere moral cel putin, sa o dati si voi mai departe. Modificata. Cat mai putin. In asa fel incat sa respecte anumite proprietati.
 
Se da o permutare. Sa se realizeze cat mai putine interschimbari de cate 2 elemente consecutive din permutare, in asa fel incat, pentru permutarea finala, $P{~i~} - P{~i-1~} = 1$ pentru cel putin $N - 2$ indici $i$ intre $2$ si $N$.

h2. Date de intrare

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

Fişierul de intrare $bonus3.in$ contine pe prima linie numarul $T$ de teste. Fiecare test contine pe prima linie ordinul permutarii, numarul natural $N$, si pe a doua linie permutarea, adica $N$ numere distincte intre $1$ si $N$.

h2. Date de ieşire

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

În fişierul de ieşire $bonus3.out$ se afla $T$ linii, pe fiecare linie fiind numarul minim de interschimbari cerut la testul corespunzator.

h2. Restricţii

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

* $1 ≤ T ≤ 5$
* $1 ≤ N ≤ 50.000$
* Pentru $10$ puncte, $N ≤ 7$
* Pentru inca $20$ de puncte, $N ≤ 50$
* Pentru inca $10$ puncte, una din permutarile finale pentru care se poate obtine numar minim de interschimbari este permutarea identitate $(1, 2, ..., N)$
* Pentru inca $10$ puncte, raspunsul este intotdeauna cel mult egal cu $2$

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

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

| 5
4
1 2 3 4
4
4 1 2 3
4
2 3 4 1
5
3 2 1 5 4
6
1 2 4 3 5 6
| 0
0
0
4
1

|
h3. Explicaţie

...

Sunt $T = 5$ teste. In primele 3 teste, permutarile deja respecta proprietatea ceruta, deci nu e nevoie de interschimbari.
Permutarea a patra poate fi adusa din $4$ interschimbari de elemente consecutive fie la $1 2 3 4 5$ fie la $2 3 4 5 1$.
In permutarea a cincea e suficient sa interschimbam pe $3$ cu $4$ si se obtine permutarea identitate.

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