Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | Invalid task id .in, Invalid task id .out | Sursă | Invalid task id |
Autor | Invalid task id | Adăugată de | Invalid task id |
Timp execuţie pe test | Invalid task id sec | Limită de memorie | Invalid task id kbytes |
Scorul tău | Invalid task id | Dificultate | Invalid task id |
Vezi solutiile trimise | Statistici
Invalid task id
Se dă un şir de N numere distincte a 1,a 2,..a 2. 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 ≤ 1000 000 $
- $ 1 ≤ a[i] ≤ 1000 000 $ , pentru fiecare $ 1 ≤ i ≤ N $
- orice "groapă" are cel puţin trei elemente
Exemplu
nrpits.in | nrpits.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