Rezolvare PBinfo #698

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

Cerința

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 și precizări

• 2 ≤ N ≤ 1.000.000
• 1 ≤ a[i] ≤ 1.000.000, pentru fiecare 1 ≤ i ≤ N
• orice “groapă” are cel puțin trei elemente

Exemplu:

nrpits.in

12
12 1 10 3 4 11 5 8 7 9 2 6

nrpits.out

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