시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB1000.000%

문제

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ę dodatnią liczbą całkowitą. Ż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.

입력

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

출력

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

예제 입력 1

7
3 5 7 2 1 6 4

예제 출력 1

2

출처

Camp > ILOCAMP Science Camps > ILOCAMP 2010 (Olympiad Group) 2-2번

  • 문제의 오타를 찾은 사람: doju