Diferențe pentru problema/nrapp între reviziile #1 si #15

nrapp

Numere Apropiate

== include(page="template/taskheader" task_id="nrapp") ==

Poveste și cerință...

Se da un numar natural $N$ si un sir $v$ de $N$ numere naturale. Sa se raspunda la $Q$ intrebari de genul:
 
* "D y": Care este cea mai mica pozitie [$x$], unde $x > y$, pentru care $v[x] < v[y]$ ? Daca nu exista o astfel de pozitie, raspunsul acestei intrebari este $N + 1$.
* "S y": Care este cea mai mare pozitie [$x$], unde $x < y$, pentru care $v[x] < v[y]$ ? Daca nu exista o astfel de pozitie, raspunsul acestei intrebari este [$0$].

h2. Date de intrare

Fișierul de intrare $nrapp.in$ ...

Fișierul de intrare $nrapp.in$ contine pe prima linie un numar natural [$N$], urmat in cea de-a doua linie un sir de $N$ numere naturale. Pe cea de-a treia linie se afla numarul natural [$Q$], iar pe urmatoarele $Q$ linii se gasesc codificarile celor $Q$ intrebari la care trebuie sa raspundeti.

h2. Date de ieșire

În fișierul de ieșire $nrapp.out$ ...

În fișierul de ieșire $nrapp.out$ se vor gasi $Q$ linii, linia $i$ continand raspunsul la intrebarea [$i$].

h2. Restricții

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 100.000$
* $1 ≤ v[i] ≤ 1.000.000$

h2. Exemplu
table(example).
|_. nrapp.in |_. nrapp.out |

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

| 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
| 0
5
4
2
1
9
8
9

|

h3. Explicație
 
...
 

== include(page="template/taskfooter" task_id="nrapp") ==