== 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${$~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ă".
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
În fişierul de ieşire $nrpits.out$ ...
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$
* orice "groapă" are cel puţin trei elemente
h2. Exemplu
table(example). |_. nrpits.in |_. nrpits.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 12
12 1 10 3 4 11 5 8 7 9 2 6
| 8
|
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") ==
== include(page="template/taskfooter" task_id="nrpits") ==
