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.

#include <bits/stdc++.h>

using namespace std;

int a[100001] , mi[100001] , ma[100001] , cnt , n;

int main()
{
    cin >> n;
    for(int i = 1 ; i  <= n ; i++)
    {
        cin >> a[i];
        ma[i] = max(ma[i-1] , a[i]);
    }
    mi[n] = a[n];
    for(int i = n-1; i >= 1 ; i--)
    {
        mi[i] = min(mi[i+1] , a[i]);
    }
    for(int i = 2 ; i < n ; i++)
    {
        if(a[i] >= ma[i-1] && a[i]<= mi[i+1]) cnt ++;
    }
    cout << cnt;
}