ecluze

Ecluza este o construcție hidrotehnică amenajată pe traseul unei căi navigabile, care asigură trecerea navelor între două suprafețe de apă cu niveluri diferite. O ecluză se compune dintr-un bazin numit „sas” sau „camera ecluzei”, prevăzut la ambele capete cu porţi etanşe şi dintr-o instalaţie puternică de pompare pentru umplerea sau golirea sasului până la nivelul dorit.

Specialiștii români au construit pe cursul navigabil al Dunării o succesiune de $N$ ecluze numerotate de la $1$ la $N$, care asigură condiții optime de navigare în sezoanele secetoase. Astfel, dacă o navă se află la un moment dat în ecluza $i$ și nivelul apei din ecluză diferă de nivelul apei din ecluza $i+1$, pentru a-și continua navigarea în condiții optime se face modificarea nivelului apei fie din ecluza $i$ la nivelul ecluzei $i+1$, fie se face modificarea nivelului apei din ecluza $i+1$ la nivelul ecluzei $i$.

De exemplu, dacă pentru un sector navigabil există $9$ ecluze pentru care nivelul apei este următorul:

Numărul minim de ecluze la care se impun modificări ale nivelului apei este $3$, după cum urmează:

• nivelul din ecluza $3$ este coborât până la nivelul $2$
• ecluza $4$ este umplută până la nivelul $2$
• ecluza $7$ este umplută până la nivelul $2$

Cerinţă

Cunoscând nivelul apei din cele $N$ ecluze, să se determine numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Date de intrare

Fişierul de intrare ecluze.in conține pe prima linie numărul natural $N$ ce reprezintă numărul de ecluze. Pe următoarea linie se află $h_1$, $h_2$,…, $h_N$ valori naturale separate prin câte un spațiu ce reprezintă nivelul apei corespunzător fiecărei ecluze.

Date de iesire

Fişierul de ieșire ecluze.out va conţine pe o singură linie un număr natural $M$ ce reprezintă numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Restricţii şi precizări

• $ 2 \leq N \leq 100 000$
• $ 1 \leq h_i \leq 1 000$ ($h_i$ – nivelul apei ecluzei $i$)
• pentru 20% din teste $N \leq 30$

Exemplu

ecluze.in

9
1 2 3 3 2 1 1 2 3

ecluze.out

6

Explicaţii

• ecluza $1$ este umplută până la nivelul $2$
• ecluza $2$ este umplută până la nivelul $3$
• nivelul din ecluza $4$ este coborât până la nivelul $2$
• nivelul din ecluza $5$ este coborât până la nivelul $1$
• ecluza $7$ este umplută până la nivelul $2$
• ecluza $8$ este umplută până la nivelul $3$