Fișierul intrare/ieșire	ecluze.in, ecluze.out	Sursă	Lot III Juniori 2015
Autor	Eugen Nodea	Adăugată de	Tiberiu Musat • Tiberiu02
Timp de execuție pe test	0.05 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Ecluze (Lot Juniori)

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:

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₁, h₂,…, h_N valori naturale separate prin câte un spațiu ce reprezintă nivelul apei corespunzător fiecărei ecluze.

Date de ieșire

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

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

Exemplu