Tetris Attack

Limit pamięci: 32 MB

Ostatnimi czasy w Bajtocji bardzo popularną grą stała się łamigłówka "Tetris attack". Jej uproszczona wersja ma następującą postać: Gracz otrzymuje do dyspozycji stos, na którym umieszczono elementów (jeden na drugim), oznaczonych różnymi symbolami. Przy tym każdym symbolem są oznaczone dokładnie dwa elementy na stosie. Ruch gracza polega na zamianie dwóch sąsiednich elementów miejscami. Jeśli w wyniku zamiany na stosie sąsiadują ze sobą elementy oznaczone identycznymi symbolami, to w "magiczny" sposób znikają, a elementy znajdujące się powyżej spadają w dół (być może powodując kolejne zniknięcia). Celem gracza jest opróżnienie stosu w jak najmniejszej liczbie ruchów.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia opis początkowej zawartości stosu,
• obliczy rozwiązanie wymagające minimalnej liczby ruchów,
• wypisze znalezione rozwiązanie na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita , . W kolejnych wierszach zapisana jest początkowa zawartość stosu. Wiersz -wszy zawiera jedną liczbę całkowitą - symbol elementu znajdującego się na wysokości (). Każdy symbol występuje na stosie dokładnie 2 razy. Na początku żadne dwa identyczne symbole nie występują obok siebie. Ponadto dane testowe są tak dobrane, że istnieje rozwiązanie zawierające nie więcej niż ruchów.

Wyjście

Na standardowym wyjściu należy wypisać opis rozwiązania, wymagającego minimalnej liczby ruchów. Pierwszy wiersz powinien zawierać jedną liczbę całkowitą - długość najkrótszego rozwiązania. Kolejne wierszy powinno zawierać opis rozwiązania, czyli ciąg liczb całkowitych , po jednej w każdym wierszu. Wartość oznacza, że w -tym ruchu gracz zdecydował o zamianie elementów, znajdujących się na wysokościach oraz .

Jeżeli istnieje wiele rozwiązań, to Twój program powinien wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

5
5
2
3
1
4
1
4
3
5
2

poprawną odpowiedzią jest:

2
5
2

natomiast dla danych wejściowych:

3
1
2
3
1
2
3

poprawnym wynikiem jest:

3
3
4
2

jak również:

3
4
3
2

Autor zadania: Tomasz Waleń.