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

Fiindca ar fi fost prea usor sa primiti doar 7 probleme cu pizza 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.

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, toate inversiunile sa aiba un punct comun. Formal, sa existe o pozitie $k$ in asa fel incat pentru orice pereche $(i < j)$ cu $P{~i~} > P{~j~}$, sa se garanteze ca $*1 &le; k < j*$.

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

* $1 ≤ T ≤ 5$
* $1 ≤ N ≤ 50.000$
* Pentru $10$ puncte, $N ≤ 7$

* Pentru inca $20$ de puncte, $N ≤ 100$
* 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 $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") ==