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]

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ţă

h2. Restricţii

* <= 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

* $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 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.

| 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

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.

| 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.

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