Runda 33 - Ciężkie klocki

Zawody stałe, runda 33,

Limit czasowy: 2s; Limit pamieciowy: 32MB

Ciężkie klocki

Mały Bobbie otrzymał na urodziny zestaw klocków. Jego rodzice wiedzieli dobrze, że nie jest to zbyt oryginalny prezent i gdzieś już słyszeli o dzieciach otrzymujących różne odmiany stymulujących intelektualnie klocków. Postanowili więc tym razem postawić nie na rozmiar, lecz na wagę. Każdy z fascynujących klocków ma swoją wagę, wyrażającą się liczbą całkowitą dodatnią. Żadne dwa klocki nie ważą tyle samo. Na nieszczęście dla Bobbiego jego rodzice są miłośnikami zagadek logicznych, postanowili więc przerwać jego beztrosko prymitywną zabawę i przygotować dla niego zadanie do wykonania.

Klocki zostały ustawione w rzędzie, jeden obok drugiego. Rodzice wyjaśnili Bobbiemu że klocki są tak skonstruowane, że jeśli któryś z nich zostanie popchnięty w jedną ze stron, to przewróci wszystkie lżejsze od niego (na zasadzie domina) po tej stronie, aż do pierwszego klocka cięższego niż ten popchnięty, bądź do pierwszego miejsca, gdzie jest przewrócony wcześniej klocek. Z uśmiechami na ustach zaproponowali Bobbiemu, że jeśli uda mu się znaleźć sposób na przewrócenie wszystkich klocków w najmniejszej możliwej liczbie "popchnięć", to będzie mógł powrócić do swych poprzednich infantylnych zabaw.

Oczywiście Bobbie ani myśli się tym zajmować, woli oglądać wzorki na dywanie. Ale Ty możesz podjąć wspaniały zamiar i pomóc Bobbiemu poprzez napisanie programu, który odnajdzie żądaną liczbę popchnięć klocków.

Wejście:

Pierwsza linia wejścia zawiera liczbę całkowitą - liczbę klocków. (). W kolejnej linii znajduje się różnych liczb całkowitych z przedziału od do - wagi kolejnych klocków ustawionych w rzędzie.

Wyjście:

Jedyna linia wyjścia powinna zawierać jedną liczbę - najmniejszą liczbę popchnięć klocków potrzebną do przewrócenia ich wszystkich.

Przykład:

Wejście:

Wyjście:

2