# PBinfo #2733 – nrapp – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dă un număr natural N si un șir v de N numere naturale. Sa se răspundă la Q întrebări de tipul:


D y: Care este cea mai mică poziție x, unde x > y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi N + 1.
S y: Care este cea mai mare poziție x, unde x < y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi 0.

Date de intrare
Fișierul de intrare nrapp.in conține pe prima linie numărul natural N, iar pe a doua linie N numere naturale separate prin spații. A treia linie va conține numărul natural nenul Q și apoi Q întrebări precum cele descrise anterior.

Date de ieșire
Fișierul de ieșire nrapp.out va conține Q linii, anume răspunsul pentru fiecare întrebare în parte.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ v[i] ≤ 1.000.000

Exemplu:
nrapp.in

8
1 3 6 5 2 1 9 6
8
S 1
D 2
D 3
S 4
S 5
D 6
D 7
D 8
nrapp.out

0
5
4
2
1
9
8
9

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int S[100005], D[100005], v[100005];
int main()
{
    ifstream fin("nrapp.in");
    ofstream fout("nrapp.out");
    int n, vf, stiva[100005]; fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
    vf = 0; stiva[vf] = n + 1;
    for(int i = n; i >= 1; --i) {
        while(vf > 0 && v[i] <= v[stiva[vf]]) --vf;
        D[i] = stiva[vf];
        stiva[++vf] = i;
    }
    vf = 0; stiva[vf] = 0;
    for(int i = 0; i <= n; ++i) {
        while(vf > 0 && v[i] <= v[stiva[vf]]) --vf;
        S[i] = stiva[vf];
        stiva[++vf] = i;
    }
    char c; fin >> n;
    for(int i = 0; i < n; ++i)
    {
        fin >> c >> vf;
        if(c == 'S')
            (fout << S[vf]).put('\n');
        else
            (fout << D[vf]).put('\n');
    }
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2733)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2733/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2733/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)