Fişierul intrare/ieşire:nrpits.in, nrpits.outSursăLot Juniori Deva 2013, baraj 1
AutorIonel-Vasile Pit-RadaAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Nrpits

Se dă un şir de N numere distincte a1, a2 ,... an. Orice secvenţă ai, ai+1, ..., aj-1, aj, 1≤i+1<j≤n ,pentru care toate valorile ak, i<k<j, sunt mai mici decât extremităţile ai şi aj, 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 ≤ 106
  • 1 ≤ ai ≤ 106, pentru fiecare 1≤i≤N
  • orice "groapă" are cel puţin trei elemente

Exemplu

nrpits.innrpits.out
12
12 1 10 3 4 11 5 8 7 9 2 6
8

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?