jucarii

Un copil are $N$ jucării pe care, fiind copil de informatician, le-a numerotat de la $1$ la $N$. El își ține jucăriile în dulap, în niște cutii, câte două jucării în fiecare cutie, cu excepția ultimei cutii, în care stă o singură jucărie dacă $N$ este impar.

Copilul și-a planificat ordinea în care vrea să se joace diseară cu jucăriile: $a_1, a_2, \ldots, a_M$ (un vector de $M$ numere naturale între $1$ și $N$, nu neapărat distincte). Totuși, camera este mică și copilul poate scoate din dulap o singură cutie odată. Ori de câte ori jucăria cu care urmează să se joace este în dulap (inclusiv prima dată), el trebuie să deschidă dulapul, să pună la loc în dulap cutia de afară (dacă există vreo cutie afară), și abia apoi să scoată cutia cu jucăria dorită. În așteptarea serii, copilul se hotărăște să-și reorganizeze jucăriile în cutii.

Cerință

Găsiți o așezare a jucăriilor în cutii care să minimizeze numărul de deschideri ale dulapului.

Date de intrare

Fișierul de intrare jucarii.in conține pe prima linie numerele $N$ și $M$, iar pe a doua linie valorile $a_1 \ a_2 \ \ldots \ a_M$, despărțite prin spații.

Date de ieșire

În fișierul de ieșire jucarii.out tipăriți pe prima linie numărul minim de deschideri ale dulapului. Pe a doua linie afișați o așezare optimă în cutii sub forma a $N$ numere, $p_1 \ p_2 \ \ldots \ p_N$, despărțite prin spații, cu semnificația că:

• Jucăriile cu numerele $p_1$ și $p_2$ stau în prima cutie.
• Jucăriile cu numerele $p_3$ și $p_4$ stau în a doua cutie.
• $\ldots$
• Dacă $N$ este par, atunci jucăriile $p_{N-1}$ și $p_N$ stau în ultima cutie.
• Dacă $N$ este impar, atunci jucăria $p_N$ stă singură în ultima cutie.

Dacă există mai multe soluții, afișați-o pe oricare.

Restricții și precizări

• $3 \leq N \leq 20$;
• $1 \leq M \leq 100 \ 000$;
• $1 \leq a_i \leq N$ pentru orice $1 \leq i \leq M$.

Exemplu

jucarii.in

8 14
1 2 5 3 5 3 7 3 7 3 7 8 7 8

jucarii.out

7
7 8 5 3 2 1 4 6

Explicație

Copilul grupează jucăriile $7$ cu $8$, $5$ cu $3$, $2$ cu $1$, $4$ cu $6$. Apoi deschide dulapul de $7$ ori, astfel:

• Scoate cutia $(2, 1)$, se joacă cu $1$, $2$.
• Scoate cutia $(5, 3)$, se joacă cu $5$, $3$, $5$, $3$.
• Scoate cutia $(7, 8)$, se joacă cu $7$.
• Scoate cutia $(5, 3)$, se joacă cu $3$.
• Scoate cutia $(7, 8)$, se joacă cu $7$.
• Scoate cutia $(5, 3)$, se joacă cu $3$.
• Scoate cutia $(7, 8)$, se joacă cu $7$, $8$, $7$, $8$.