B55 - Difference Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

以下の 2 種類のクエリを高速に処理するプログラムを実装してください。

  • クエリ 1：x と書かれたカードが机に置かれる。
  • クエリ 2：整数 x と「机にあるカード」の差の絶対値の最小値を答える。

ただし、最初の時点では机の上に 1 個もカードが置かれていないものとします。

入力

Query_i は i 回目のクエリの情報を表します。クエリ 1 の場合は 1 x、クエリ 2 の場合は 2 x という形式で与えられます。

詳しくは入力例をご覧ください。

Q
Query_1
:
Query_Q

出力

クエリ 2 の答えを、順番に出力してください。ただし、机の上にカードが存在しないクエリについては、-1 と出力してください。

制約

  • 1 \leq Q \leq 100,000
  • 1 \leq x \leq 10^9
  • クエリ 1 では、既に置かれているカードが追加されることはない

入力例 1

5
2 30
1 10
2 30
1 40
2 30

出力例 1

-1
20
10