BoB005-E: Discard This Card

2 secs 1024 MB
kyaneko999

問題


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

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

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

制約


  • 入力はすべて整数
  • または
  • のうち少なくとも 1 つは
  • ならば
  • ならば

入力


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





出力


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

入出力例


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

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

Submit


Go (1.14)