C - データ構造 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

数の集合 S に対する以下のクエリを処理してください。

  • タイプ 1S に数 X を追加する。
  • タイプ 2S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。

入力

入力は以下の形式で標準入力から与えられる。

Q
T_1 X_1
T_2 X_2
:
T_Q X_Q
  • 1 行目には、クエリの個数を表す整数 Q (1 ≦ Q ≦ 200,000) が与えられる。
  • 2 行目からの Q 行には、クエリの情報が与えられる。このうち i 行目では、2 つの整数 T_i (1 ≦ T_i ≦ 2), X_i (1 ≦ X_i ≦ 200,000) が空白区切りで与えられる。これは、
    • T_i = 1 の場合、「S に数 X_i を追加する」というクエリを表す。ただし、クエリを処理する前の S には X_i が含まれていないことが保証される。
    • T_i = 2 の場合、「S に含まれる数のうち X_i 番目に小さい数を答え、その数を S から削除する」というクエリを表す。ただし、クエリを処理する前の S に含まれる数の個数が X_i 個以上であることが保証される。

出力

タイプ 2 のクエリの個数を Q_2 とすると、出力は Q_2 行からなる。このうち i 行目には、タイプ 2 のクエリのうち i 番目のものに対する答えを出力せよ。出力の末尾にも改行を入れること。


入力例1

5
1 11
1 29
1 89
2 2
2 2

出力例1

29
89

入力例2

12
1 8932
1 183450
1 34323
1 81486
1 127874
1 114850
1 55277
1 112706
2 3
1 39456
1 52403
2 4

出力例2

55277
52403