Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:

• 1 x – adaugă numărul x în A
• 2 k – dacă A ar fi ordonat crescător, care ar fi a k-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 lui k este mai mică sau egală decât numărul de elemente din A.
• 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.