egal


Timp maxim de execuţie/test:
0.2 secunde
Memorie totala disponibilă/stivă:
32 MB/1 MB

Fie A o secventa de N numere naturale. Asupra acestei secvente pot fi aplicate una sau mai multe operatii de incrementare.
O operatie de incrementare consta în selectarea unei subsecvente a secventei A formata NUMAI din elemente egale si marirea cu 1 a tuturor elementelor din subsecventa.

Cerinţă

Scrieti un program care determina numarul minim de operatii de incrementare necesare pentru a egaliza toate elementele secventei A.

Date de intrare

Fişierul de intrare egal.in contine pe prima linie numarul natural N. Pe cea de a doua linie se afla N numere naturale separate prin spatii reprezentând elementele secventei A.

Date de ieşire

Fişierul de ieşire egal.out va conţine o singura linie pe care va fi scris un singur numar natural reprezentând numarul minim de operatii de incrementare necesare pentru a egaliza toate elementele secventei A.

Restricţii

  • 1 <= N <= 200000
  • 0 <= Elementele secventei A <= 109

Exemple

egal.in egal.out Explicatie
4
1 2 4 2
 5 Operatiile de incrementare aplicate sunt:
Subsecventa A1..1 rezulta 2 2 4 2
Subsecventa A1..2 rezulta 3 3 4 2
Subsecventa A1..2 rezulta 4 4 4 2
Subsecventa A4..4 rezulta 4 4 4 3
Subsecventa A4..4 rezulta 4 4 4 4
prof. Emanuela Cerchez
Liceul de Informatică „Grigore Moisil” Iaşi
emanuela.cerchez@gmail.com