Klucze

Limit pamięci: 32MB

Bajklucz - firma dorabiająca klucze prywatne do ssh, kupiła nową maszynę i zleciła Ci napisanie jej oprogramowania. Maszyna mając płytkę, potrafi wycinać w niej dowolny prostokąt.
Na poczatku dostajesz płytkę o wymiarach d (szerokość klucza) na nieskonczonosc. Twoim zadaniem jest określenie, ile minimalnie cięć maszyna musi wykonać. Bajklucz dysponuje już maszyną, określającą dla każdego punktu jednostkowego [1, d] ile wystaje z podstawy klucza.


#      #
## ## ##
## ## ##                           
##################################
##################################

Wejście:

Pierwsza linia zawiera liczbę d (d<=1000000) oznaczająca szerokość klucza. W następnym wierszu znajduję się d liczb całkowitych h_i (h_i<=10^9) oznaczające ile wystaje z bazy klucza na pozycji i.

Wyjście:

Twój program powinien wypisać jedną liczbę całkowitą - minimalną liczbę cięć, jakie musi wykonać maszyna.

Przykład:

Wejscie:
8
3 2 0 2 2 0 2 3

Wyjscie:
4

Klucz autora:
4 0 0 2 3 7 4 2 2 2