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.

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

h2. Date de intrare