Klocki

Limit pamięci: 32 MB

Bajtazar jako małe dziecko uwielbiał bawić się klockami. Jego zabawa polegała na układaniu z klocków kolumn o losowo wybranych wysokościach, a następnie ich porządkowaniu. Bajtazar wybierał liczbę , a następnie starał się w minimalnej liczbie ruchów tak uporządkować klocki, by pewne kolejnych kolumn klocków miało tę samą wysokość. Pojedynczy ruch polega na:

• położeniu jednego klocka na szczycie wybranej kolumny klocków (Bajtazar posiadał ogromne pudło z zapasowymi klockami, więc ten ruch jest zawsze możliwy), lub
• zdjęciu jednego klocka ze szczytu wybranej kolumny.

Bajtazar nigdy nie był pewien czy wybrane przez niego rozwiązanie było optymalne i poprosił Cię o napisanie programu, który pomoże mu rozwiązywać ten problem.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia liczbę i opis początkowego układu klocków,
• wyznaczy rozwiązanie wymagające minimalnej liczby ruchów,
• wypisze otrzymane rozwiązanie na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem. W kolejnych wierszach zapisane są początkowe wysokości kolumn klocków; wiersz -wszy zawiera jedną liczbę całkowitą - wysokość -tej kolumny klocków, czyli liczbę klocków z których się ona składa.

Wyjście

Na standardowe wyjście należy wypisać optymalne rozwiązanie, to jest układ klocków, który:

• zawiera kolejnych kolumn o tej samej wysokości,
• można otrzymać z początkowego układu w minimalnej liczbie ruchów.

Przykład

Dla danych wejściowych:

5 3
3
9
2
3
1

poprawną odpowiedzią jest:

2
3
9
2
2
2

Autor zadania: Tomasz Waleń.