Fişierul intrare/ieşire:	nrpits.in, nrpits.out	Sursă	Lot Juniori Deva 2013, baraj 1
Autor	Ionel-Vasile Pit-Rada	Adăugată de	Marian Darius •dariusdarius
Timp execuţie pe test	0.3 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Nrpits

Se dă un şir de N numere distincte a₁, a₂ ,... 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.

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.

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.

Restricţii

• 2 ≤ N ≤ 10⁶

• 1 ≤ a_i ≤ 10⁶, pentru fiecare 1≤i≤N

• orice "groapă" are cel puţin trei elemente

Exemplu

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

Cum se trimit solutii?