Question

#2623 LR

Aveți la dispoziție un șir a[1], a[2], …, a[n] de numere naturale. Un element a[i] (2 ≤ i ≤ n - 1) îl numim LR dacă a[i] are toate elementele din șir aflate la stânga sa mai mici sau egale și toate elementele din dreapta sa mai mari sau egale cu a[i]. De exemplu, în șirul a = (6, 3, 1, 2, 6, 10, 7, 11, 16) sunt două elemente LR, valorile 6 și 11 de la pozițiile 5 și 8.

Cerința
Să se determine numărul elementelor LR din șir.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând elementele șirului.

Date de ieșire
Programul va afișa pe ecran numărul C, reprezentând numărul elementelor LR din șir.

Restricții și precizări
3 ≤ n ≤ 100 000
cele n numere citite vor fi mai mici decât 1.000.000
Nu uitați că elementele a[1] și a[n] nu sunt LR.



Exemplu
Intrare

12
6 4 2 7 10 8 9 14 29 30 52 50
Ieșire

4
Explicație
Numerele LR din șir se află la pozițiile 4, 8, 9, 10.

Answer 1

#include <iostream>

#include <algorithm>

using namespace std;

int v[100001],v1[100001];

int main(){

   int c=0,i,n;

   cin>>n;

   cin>>v[1];v1[1]=v[1];

   for( i=2; i<=n; i++)

       {cin>>v[i];v1[i]=max(v[i],v1[i-1]);

       }

   for( i=2; i<n; ++i)

       if(v1[i]>v1[i-1]&&v1[i]<v1[i+1])

               c++;

    cout<<c;

    return 0;

}