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

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema LR:

#include <bits/stdc++.h>
#define nmax 100003
using namespace std;

int a[nmax], st[nmax], dr[nmax], n;

int main()
{
    int i, cnt = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];

    st[1] = 1;
    for (i = 2; i <= n; i++)
        st[i]= max(a[i], st[i - 1]);
    dr[n] = a[n];
    for (i = n - 1; i >= 1; i--)
        dr[i] = min(a[i], dr[i + 1]);

    for (i = 2; i < n; i++)
        if (st[i] == dr[i]) cnt++;
    cout << cnt << "\n";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2623 LR

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2623 LR de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2623 LR