sortare00

Se dă un șir de numere $a_0, a_1, a_2, \ldots, a_{n+1}$ în care primele două numere sunt egale cu $0$, iar restul sunt din mulțimea $1, 2, 3, \ldots, n$ și formează o permutare. Ne dorim să ordonăm crescător acest șir. În acest scop, se pot efectua interschimbări. O interschimbare este specificată printr-o poziție $k$ $(0 \leq k \leq n)$ și are semnificația că secvența formată din numerele nenule $a_k \ a_{k+1}$ se interschimbă cu secvența $0 \ 0$. Interschimbarea va păstra ordinea dintre elementele nenule implicate $(a_k$ și $a_{k+1})$.

Cerință

Scrieți un program care, cunoscând șirul, determină o succesiune de interschimbări care conduc la ordonarea crescătoare a elementelor șirului.

Date de intrare

Fișierul de intrare sortare00.in conține pe prima linie numărul natural $n$, reprezentând numărul numerelor nenule din șirul dat. Pe linia a doua se află cele $n$ numere nenule, reprezentând permutarea, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire sortare00.out conține pe prima linie numărul de interschimbări efectuate pentru a obține șirul ordonat crescător, iar pe linia a doua sunt scrise interschimbările separate prin câte un spațiu.

Restricții și precizări

• $3 < n < 10 \ 000$
• Numărul de interschimbări efectuate trebuie să fie $\leq 10^5$
• Pentru datele de test se garantează că există soluție.
• Dacă interschimbările din fișierul de ieșire conduc la sortarea crescătoare a elementelor șirului, punctajul primit va fi diferențiat pe baza numărului $nr$ de interschimbări efectuate, astfel:
  • dacă $nr \leq 4 \cdot n$, atunci se acordă punctajul maxim pe test
  • dacă $4 \cdot n < nr \leq 6 \cdot n$, atunci se acordă $75\%$ din punctajul maxim pe test
  • dacă $6 \cdot n < nr \leq 8 \cdot n$, atunci se acordă $50\%$ din punctajul maxim pe test
  • în rest pentru $8 \cdot n < nr \leq 10^5$ atunci se acordă $25\%$ din punctajul maxim pe test.

Exemplu

sortare00.in

5
3 2 1 5 4

sortare00.out

7
3 1 4 2 5 3 0

Explicație

Cele $7$ interschimbări efectuate conduc la sortarea elementelor șirului:

1. $0 \ 0 \ 3 \ 2 \ 1 \ 5 \ 4 \xrightarrow{3} 2 \ 1 \ 3 \ 0 \ 0 \ 5 \ 4$
2. $2 \ 1 \ 3 \ 0 \ 0 \ 5 \ 4 \xrightarrow{1} 2 \ 0 \ 0 \ 1 \ 3 \ 5 \ 4$
3. $2 \ 0 \ 0 \ 1 \ 3 \ 5 \ 4 \xrightarrow{4} 2 \ 3 \ 5 \ 1 \ 0 \ 0 \ 4$
4. $2 \ 3 \ 5 \ 1 \ 0 \ 0 \ 4 \xrightarrow{2} 2 \ 3 \ 0 \ 0 \ 5 \ 1 \ 4$
5. $2 \ 3 \ 0 \ 0 \ 5 \ 1 \ 4 \xrightarrow{5} 2 \ 3 \ 1 \ 4 \ 5 \ 0 \ 0$
6. $2 \ 3 \ 1 \ 4 \ 5 \ 0 \ 0 \xrightarrow{3} 2 \ 3 \ 1 \ 0 \ 0 \ 4 \ 5$
7. $2 \ 3 \ 1 \ 0 \ 0 \ 4 \ 5 \xrightarrow{0} 0 \ 0 \ 1 \ 2 \ 3 \ 4 \ 5$