Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Przekładanka (prz)

Przekładanka

Limit pamięci: 64 MB

Bajtazar kupił synkowi Bajtkowi zestaw klocków ponumerowanych od do i ustawił je w rzędzie w pewnej kolejności. Zadaniem Bajtka jest ustawienie klocków w kolejności numerów tych klocków, od najmniejszego do największego. Jedyne ruchy, jakie może wykonywać Bajtek, to:

przełożenie ostatniego klocka na początek (ruch typu a), oraz
przełożenie trzeciego klocka na początek (ruch typu b).

Pomóż Bajtkowi i napisz program, który sprawdzi, czy dany układ klocków da się w ogóle ustawić w żądanej kolejności, a jeżeli tak, to poda, jak to zrobić.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita , . W drugim wierszu znajduje się liczb całkowitych z zakresu od do pooddzielanych pojedynczymi odstępami. Liczby te nie powtarzają się i reprezentują początkowe ustawienie klocków.

Wyjście

Jeśli nie istnieje sekwencja ruchów prowadząca do ustawienia klocków w porządku rosnącym numerów, Twój program powinien wypisać na standardowe wyjście "NIE DA SIE" (bez cudzysłowów).

W przeciwnym przypadku, w pierwszym wierszu wyjścia powinna znaleźć się jedna liczba całkowita (), oznaczająca liczbę wykonywanych operacji. Przez operację rozumiemy -krotne wykonanie jednego z ruchów a lub b.

Jeżeli , to w drugim wierszu powinien znaleźć się ciąg liczb całkowitych z dodanymi pojedynczymi znakami a lub b. Zapis postaci a (dla ) oznacza -krotne wykonanie ruchu a. Zapis postaci b (dla ) oznacza -krotne wykonanie ruchu b.