\(K\) 番目以下の数値を保持する赤黒木1と \(K\) 番目以降の数値を保持する赤黒木2を用意する.

クエリ1がきたときは以下のように処理する.

  • 赤黒木1のサイズが \(K\) 未満ならば赤黒木1に \(v\) を挿入する.
  • 赤黒木1の最大値が \(v\) 未満ならば赤黒木2に \(v\) を挿入する.
  • 赤黒木1の最大値を削除し, これを赤黒木2に挿入する. そして赤黒木1に \(v\) を挿入する.

クエリ2がきたときは以下のように処理する.

  • 赤黒木1のサイズが \(K\) 未満ならば -1 を出力する.
  • 赤黒木1の最大値を削除し, これを出力する. そして赤黒木1に赤黒木2の最小値を削除して挿入する.