E - Balls and Bag Query 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

空の袋があります。 クエリが Q 個与えられるので、順番に処理してください。

クエリは次の 3 種類です。

  • 1 x : 整数 x が書かれたボールを 1 つ袋に入れる。
  • 2 x : 整数 x が書かれたボールを 1 つ袋の中から取り出して外に捨てる。このクエリが与えられるとき、袋の中に整数 x が書かれたボールが存在することが保証される。
  • 3 : 袋の中にあるボールに書かれている整数の種類数を出力する。

制約

  • 1 \leq Q \leq 2 \times 10^{5}
  • 1 \leq x \leq 10^{6}
  • 2 種類目のクエリが与えられるとき、袋の中に整数 x が書かれたボールが存在する。
  • 3 種類目のクエリが 1 つ以上存在する。
  • 入力はすべて整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i は以下の 3 つの形式のいずれかで与えられる。

1 x

2 x

3

出力

3 種類目のクエリが K 個あるとき、K 行出力せよ。 i 行目(1 \leq i \leq K) では、i 番目の 3 種類目のクエリに対する答えを出力せよ。

入力例 1

8
1 3
1 1
1 4
3
2 1
3
1 5
3

出力例 1

3
2
3

はじめ、袋の中は空です。

1 番目のクエリ 1 3 で袋の中に 3 が書かれたボールが 1 つ入ります。

2 番目のクエリ 1 1 で袋の中に 1 が書かれたボールが 1 つ入ります。

3 番目のクエリ 1 4 で袋の中に 4 が書かれたボールが 1 つ入ります。

4 番目のクエリ 3 で袋の中に 1, 3, 4 の 3 種類のボールが入っているため、3 を出力します。

5 番目のクエリ 2 1 で袋の中から 1 が書かれたボールを 1 つ取り出します。

6 番目のクエリ 3 で袋の中に 3, 4 の 2 種類のボールが入っているため、2 を出力します。

7 番目のクエリ 1 5 で袋の中に 5 が書かれたボールが 1 つ入ります。

8 番目のクエリ 3 で袋の中に 3, 4, 5 の 3 種類のボールが入っているため、3 を出力します。

入力例 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

出力例 2

1
1

Score : 300 points

Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

  • 1 x : Put one ball with the integer x written on it into the bag.
  • 2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
  • 3 : Print the number of different integers written on the balls in the bag.

Constraints

  • 1 \leq Q \leq 2 \times 10^{5}
  • 1 \leq x \leq 10^{6}
  • When a query of the second type is given, the bag has a ball with the integer x written on it.
  • There is at least one query of the third type.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i is given in one of the following three formats:

1 x

2 x

3

Output

If there are K queries of the third type, print K lines. The i-th line (1 \leq i \leq K) should contain the answer to the i-th query of the third type.

Sample Input 1

8
1 3
1 1
1 4
3
2 1
3
1 5
3

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

Sample Output 2

1
1