Ana si Barbu se joacă din nou. Acum ei au n cuburi. Pe fiecare cub este scris un număr natural cuprins între 1 şi n, astfel încât oricare două cuburi au numere diferite.
Pe tabla de joc este desenat un şir format din n patrate, numerotate de la stânga la dreapta de la 1 la n. În aceste pătrate pot fi plasate cuburi, un singur cub într-un pătrat.
Iniţial, Ana pune pe tabla de joc nişte cuburi, în unele dintre pătrate. Apoi Barbu are voie să aşeze cuburile rămase în pătratele rămase, aşa cum doreşte el.
După ce toate cuburile sunt aşezate pe tabla de joc, Ana trebuie să execute cât timp este posibil operaţii de tipul următor: "dacă numărul scris pe ultimul cub (cel aflat pe tablă în pătratul cu numărul n) este x, atunci secvenţa formată din ultimele x cuburi se inversează".
Evident, jocul se termină când în pătratul cu numărul n se va afla pătratul cu numărul 1.
De exemplu, să considerăm că în joc există n=5 cuburi. Iniţial, Ana plasează cuburile cu numerele 2 şi 3 în pătratele 5 şi respectiv 3.
Configuraţia iniţială a tablei de joc este 00302 (cu 0 am marcat un patrat gol).
Barbu analizează tabla de joc şi aşează cuburile rămase astfel: 41352
In acest caz Ana va trebui să facă 5 operaţii: 41325
52314
54132
54123
54321
Şi jocul s-a încheiat.
Cerinţă
Scrieţi un program care să îl ajute pe Bogdan să aşeze cuburile astfel încât Ana să facă un număr maxim de operaţii.
Date de intrare
Fişierul de intrare cubinvers.in conţine pe prima linie numărul natural n. Pe cea de a doua linie sunt scrise n numere naturale separate prin spaţiu reprezentând configuraţia iniţială a tablei de joc (0 semnifică un pătrat gol, o valoare diferită de 0 reprezintă numărul cubului plasat în pătratul corespunzător).
Date de ieşire
Fişierul de iesire cubinvers.out va conţine două linii. Pe prima linie va fi scris numărul maxim de operaţii pe care le va executa Ana pentru configuraţia construită de Bogdan.
Pe cea de a doua linie vor fi scrise n numere naturale distincte cuprinse între 1 şi n, separate prin câte un spaţiu, reprezentând configuraţia construită de Bogdan, pentru care Ana face număr maxim de operaţii. Al i-lea număr de pe cea de-a doua linie reprezintă numărul cubului plasat pe tabla de joc în pătratul i.
Restricţii
1 <= n <= 25
Configuraţia iniţială din fişierul de intrare conţine cel mult 10 pătrate goale.
Dacă există mai multe soluţii posibile, puteţi afişa oricare dintre acestea.