== include(page="template/taskheader" task_id="operatii") ==
Poveste si cerinta...
Consideram un vector nul cu $N$ elemente ( fiecare element este egal cu $0$ ). Asupra vectorului se efectueaza un numar de operatii de forma: se selecteaza doi indici $i$ si $j$, {$i ≤ j$}, si se incrementeaza cu o unitate toate elementele din vector dintre pozitiile $i$ si $j$ inclusiv.
Dandu-se un vector $v$ cu $N$ elemente, sa se precizeze care este numarul minim de operatii de tipul celei precizate mai sus care trebuiesc efectuate pentru a ajunge de la vectorul nul la vectorul $v$.
h2. Date de intrare
Fisierul de intrare $operatii.in$ ...
Fisierul de intrare $operatii.in$ contine pe prima linie numarul $N$. Cea de a doua linie contine $N$ numere naturale, reprezentand elementele vectorului $v$.
h2. Date de iesire
In fisierul de iesire $operatii.out$ ...
In fisierul de iesire $operatii.out$ se va scrie pe prima linie numarul minim de operatii care trebuiesc efectuate asupra vectorului nul pentru a obtine vectorul $v$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000 000$
* Fiecare numar din $v$ este mai mic sau egal cu {$100 000$}
* Se considera ca primul element al oricarui vector este situat pe pozitia $1$
* Pentru 10% din teste, $N ≤ 10$
* Pentru 30% din teste, $N ≤ 1 000$
* Pentru 40% din teste se garanteaza ca rezultatul nu va depasi $3 000$
h2. Exemplu
table(example). |_. operatii.in |_. operatii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|7
0 2 2 1 0 1 2
|4|
h3. Explicatie
...
table(example). |_. vector |_. operatia efectuata |
|0 0 0 0 0 0 0|i = 2, j = 4|
|0 1 1 1 0 0 0|i = 2, j = 3|
|0 2 2 1 0 0 0|i = 6, j = 7|
|0 2 2 1 0 1 1|i = 7, j = 7|
|0 2 2 1 0 1 2||
== include(page="template/taskfooter" task_id="operatii") ==
