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.0001 ≤ a[i] ≤ 1.000.000, pentru fiecare1 ≤ 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 1010 3 412 1 10 3 4 1110 3 4 1111 5 88 7 99 2 611 5 8 7 9
#include <fstream>
#include <stack>
using namespace std;
stack <int> s;
int main()
{ifstream cin("nrpits.in");
ofstream cout("nrpits.out");
int n,a,cnt=0;
cin>>n>>a;
s.push(a);
for(int i=2;i<=n;i++)
{
cin>>a;
if(s.empty())
s.push(a);
else{
while(!s.empty()&&a>s.top())
{
if(s.size()>=2&&i>=3)
cnt++;
s.pop();
}
s.push(a);}
}
cout<<cnt;
return 0;
}