Se consideră un șir A
, inițial vid. Asupra lui A
se aplică n
operații de două tipuri:
1 x
– adaugă numărulx
înA
2 k
– dacăA
ar fi ordonat crescător, care ar fi ak
-a valoare?
Cerința
Să se răspundă la cele n
întrebări.
Date de intrare
Fișierul de intrare bstq.in
conține pe prima linie numărul n
, iar pe următoarele n
linii se află câte o operație de tip 1
sau 2
.
Date de ieșire
Fișierul de ieșire bstq.out
va conține atâtea linii câte operații de tip 2
sunt în fișierul de intrare.
Restricții și precizări
1 ≤ n ≤ 200.000
- Numerele care se adaugă în
A
sunt numere întregi reprezentate pe 32 de biți cu semn. - Este garantat că la orice operație
2 k
valoarea luik
este mai mică sau egală decât numărul de elemente dinA
. - Este garantat că numerele care se introduc în
A
prin operația de tip 1 sunt generate aleator.
Exemplu:
bstq.in
16 1 7 1 9 1 3 1 7 2 3 2 2 1 10 1 2 2 4 2 5 1 5 2 3 1 8 1 10 1 4 1 3
bstq.out
7 7 7 9 5
Explicație
La prima întrebare, 2 3
, deja în A
sunt valorile 3,7,7,9
, deci a treia valoare este 7
.
La a doua întrebare, 2 2
, A = 3,7,7,9
, deci a doua valoare este 7
.
La a treia întrebare, 2 4
, A = 2,3,7,7,9,10
, deci a patra valoare este 7
.
La a patra întrebare, 2 5
, A = 2,3,7,7,9,10
, deci a cincea valoare este 9
.
La a cincea întrebare, 2 3
, A = 2,3,5,7,7,9,10
, deci a treia valoare este 5
.