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

h3. Explicaţie

Sunt $T = 5$ teste. In primele 3 teste, permutarile deja respecta proprietatea ceruta, deci nu e nevoie de interschimbari. Pentru prima permutare orice $k$ e valid (pentru ca nu exista inversiuni). Pentru a doua, $k = 1$ e solutie (toate inversiunile sunt realizate de $4$ cu elemente din dreapta), iar pentru a treia $k = 3$ respecta conditia (toate inversiunile sunt realizate de $1$ cu elemente din stanga)

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.