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

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

ş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