== include(page="template/taskheader" task_id="nrpits") ==
Se dă un şir de $N$ numere distincte $a${$~1~$}, $a${$~2~$} ,... $a${$~n~$}. Orice secvenţă $a${$~i~$}, $a${$~i+1~$}, ..., $a${$~j-1~$}, $a${$~j~$}, $1≤i+1<j≤n$ ,pentru care toate valorile $a${$~k~$}, $i<k<j$, sunt mai mici decât extremităţile $a${$~i~$} şi $a${$~j~$}, o vom numi în continuare "groapă".
Se dă un şir de N numere distincte a ~1~,a ~2~,..a ~2~. Orice secvenţă
a ~i~,a ~i+1~,...,a ~j-1~,a ~j~, 1 ≤ i + 1 < j ≤ n, pentru care toate valorile a ~k~,
i < k < j, sunt mai mici decât extremităţile a ~i~ şi a ~j~, o vom numi în continuare "groapă".
Scrieţi un program care va determina numărul "gropilor" din şirul dat.
Scrieţi un program care va determina numărul "gropilor" din şirul dat.
h2. Date de intrare
Fişierul de intrare $nrpits.in$ conţine pe prima linie numărul natural $N$. Pe linia a doua se află scrise cele $N$ numere naturale ale şirului, separate prin spaţiu.
Fişierul de intrare $nrpits.in$ conţine pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere naturale ale şirului, separate prin spaţiu.
h2. Date de ieşire
Fişierul de ieşire $nrpits.out$ va conţine un singur număr reprezentând numărul de "gropi" ale şirului dat.
Fişierul de ieşire nrpits.out va conţine un singur număr reprezentând numărul de "gropi" ale şirului dat.
h2. Restricţii
* $2 ≤ N ≤ 10^6^$
* $1 ≤ a{~i~} ≤ 10^6^$, pentru fiecare $1≤i≤N$
* 2 ≤ N ≤ 1000 000
* 1 ≤ a[i] ≤ 1000 000, pentru fiecare 1 ≤ i ≤ N
* orice "groapă" are cel puţin trei elemente
table(example). |_. nrpits.in |_. nrpits.out |
| 12
12 1 10 3 4 11 5 8 7 9 2 6
| 8
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Cele opt "gropi" sunt:
$12 1 10$,
$10 3 4$,
$12 1 10 3 4 11$,
$10 3 4 11$,
$11 5 8$,
$8 7 9$,
$9 2 6$,
$11 5 8 7 9$
...
== include(page="template/taskfooter" task_id="nrpits") ==
