Munte7

munte7

== include(page="template/taskheader" task_id="munte7") ==

Se dă un şir de $N$ numere naturale care trebuie adus la forma de “munte”. Un şir are formă de munte dacă există $1 <= i <= n$ astfel încât:
- oricare ar fi $j$, $1 <= j < i, v[j] <= v[j + 1]$
- oricare ar fi $k$, $i <= k < n, v[k] >= v[k + 1]$
Cu alte cuvinte, un şir are formă de munte dacă este crescător până la o pozitie $i$ şi apoi descrescător până la sfârşit.
 
h2. Cerinţă
 
Să se calculeze numărul minim de numere care trebuiesc modificate pentru ca şirul rezultat să aibă formă de munte.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $munte7.in$ contine pe prima linie numărul $N$ = numărul de numere din şir. Pe a doua linie se for găsi cele $N$ numere ale şirului.

Fişierul de intrare $munte7.in$ ...

h2. Date de ieşire

Fişierul de ieşire $munte7.out$ va contine pe prima linie numărul de modificări necesare pentru a-i da şirului forma de “munte”.

În fişierul de ieşire $munte7.out$ ...

h2. Restricţii

* $2 <= N <= 200000$
* Elementele şirului sunt numere intregi care au valoarea absolută $<= 10^9^$
* Pentru $40%$ din teste $N <= 2000$
* Pentru restul de $60%$, $N <= 200000$

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. munte7.in |_. munte7.out |_. Explicatii |
| 7
-1 2 3 -1 3 2 1
| 1
| Dacă îi dăm elementului de pe poziţia 4 valoarea 3, atunci
şirul devine -1 2 3 3 3 2 1 şi are o formă de munte.
|
| 9
1 5 4 7 6 8 3 5 2
| 3
| Schimbăm elementul de pe poziţia 3 în 6, elementul
de pe poziţia 5 în 7 şi elementul de pe poziţia 7 în 6.
şirul devine 1 5 6 7 7 8 6 5 2, deci este un „munte”
cu vârf în poziţia 6.
|

table(example). |_. munte7.in |_. munte7.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="munte7") ==

== include(page="template/taskfooter" task_id="munte7") ==