BoB005-E: Discard This Card

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

最初 Sakky さんはカードを何枚か持っています.各カードには整数が 1 つ書かれています.
今から QQ 個のクエリが与えられます.ii 番目のクエリでは整数 Ti,XiT_i,X_i が与えられるので,Sakky さんは以下の処理を行います.

  • Ti=0T_i=0 のとき,現在持っているカードに書かれた数のうち,値が最大のものを答える.
  • Ti=1T_i=1 のとき,現在持っているカードのうち XiX_i が書かれたカードを 1 枚選んで捨てる.
    なお,カードを捨てる直前において,XiX_i が書かれたカードを 1 枚以上持っていることが保証される.

QQ 番目のクエリについては TQ=1T_Q=1 であり,QQ 番目のクエリを終えた時点で Sakky さんはカードを 1 枚も持っていませんでした.
Ti=0T_i=0 であるクエリにおいて Sakky さんが答えた値を順に求めてください.

制約

  • 入力はすべて整数
  • 2Q2×1052\le Q\le 2\times10^5
  • T1,T2,,TQ1T_1,T_2,\dots,T_{Q-1}00 または 11
  • T1,T2,,TQ1T_1,T_2,\dots,T_{Q-1} のうち少なくとも 1 つは 00
  • TQ=1T_Q=1
  • Ti=0T_i=0 ならば Xi=0X_i=0
  • Ti=1T_i=1 ならば 1Xi1091\le X_i\le 10^9

入力

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

QQ
T1  X1T_1\;X_1
T2  X2T_2\;X_2
\vdots
TQ  XQT_Q\;X_Q

出力

Ti=0T_i=0 であるクエリに対する答えを,クエリ順に改行区切りにして整数で出力しなさい.

入出力例

入力例1
6
0 0
1 2
0 0
1 3
0 0
1 1
出力例1
3
3
1

最初,Sakky さんは 1,2,31,2,3 が書かれたカードを 1 枚ずつ持っています.
11 番目のクエリでは,1,2,31,2,3 が書かれたカードを持っているため,値が最大である 33 を答えます.
22 番目のクエリでは,22 が書かれたカードを 1 枚捨てます.
33 番目のクエリでは,1,31,3 が書かれたカードを持っているため,値が最大である 33 を答えます.
44 番目のクエリでは,33 が書かれたカードを 1 枚捨てます.
55 番目のクエリでは,11 が書かれたカードしか持っていないため 11 を答えます.
66 番目のクエリでは,11 が書かれたカードを 1 枚捨てます.この時点で,Sakky さんはカードを 1 枚も持っていません.

Submit


Go (1.21)