nrpits

Se dă un șir de $N$ numere distincte $a_1 ,a_2, \dots, a_N$. Orice secvență $a_i, a_{i+1}, \dots, a_{j-1}, a_j$, $1 \leq i + 1 < j \leq 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ţă

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 \leq N \leq 1 \ 000 \ 000$
• $1 \leq a_i \leq 1 \ 000 \ 000$, pentru fiecare $1 \leq i \leq N$
• orice "groapă" are cel puțin trei elemente

Exemplul 1

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)$.