C - Understory 解説 /

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

配点 : 300 点

問題文

高橋くんは、庭にある木の本数を管理しています。はじめ、庭に木は 1 本もありません。

Q 個のクエリが順に与えられます。クエリは次の 2 種類のいずれかです。各クエリを処理した直後に庭にある木の本数を出力してください。

  • 1 h : 庭に高さ h の木を新たに 1 本追加する。
  • 2 h : いま庭にある木のうち、高さが h 以下の木をすべて削除する。

制約

  • 1 \le Q \le 3 \times 10^5
  • 1 \le h \le 10^9
  • 入力される値は全て整数

入力

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

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

i 番目のクエリを表す \text{query}_i は以下の 2 種類のいずれかである。

1 h

2 h

出力

Q 行出力せよ。

i 行目には i 番目のクエリを処理した直後の庭にある木の本数を出力せよ。

入力例 1

5
1 5
1 7
1 8
2 7
1 3

出力例 1

1
2
3
1
2

以下のように木の本数は変化します。

  • 高さ 5 の木が追加される。庭にある木は高さ 5 の 1 本である。
  • 高さ 7 の木が追加される。庭にある木は高さ 5, 7 の 2 本である。
  • 高さ 8 の木が追加される。庭にある木は高さ 5, 7, 8 の 3 本である。
  • 高さ 7 以下の木が削除される。庭にある木は高さ 8 の 1 本である。
  • 高さ 3 の木が追加される。庭にある木は高さ 8, 3 の 2 本である。

入力例 2

12
2 256601193
1 85138616
1 202564041
2 276477192
1 55551662
1 170271057
2 754166580
1 854388209
1 772036624
2 651124113
1 301137866
2 290875185

出力例 2

0
1
2
0
1
2
0
1
2
2
3
3

Score : 300 points

Problem Statement

Takahashi is managing the number of trees in his garden. Initially, there are no trees in the garden.

Q queries are given in order. Each query is one of the following two types. Immediately after processing each query, output the number of trees currently in the garden.

  • 1 h : Add one new tree of height h to the garden.
  • 2 h : Remove all trees currently in the garden whose height is at most h.

Constraints

  • 1 \le Q \le 3 \times 10^5
  • 1 \le h \le 10^9
  • 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

\text{query}_i, representing the i-th query, is one of the following two types:

1 h

2 h

Output

Output Q lines.

The i-th line should contain the number of trees in the garden immediately after processing the i-th query.

Sample Input 1

5
1 5
1 7
1 8
2 7
1 3

Sample Output 1

1
2
3
1
2

The number of trees changes as follows.

  • A tree of height 5 is added. The garden contains one tree of height 5.
  • A tree of height 7 is added. The garden contains two trees of heights 5, 7.
  • A tree of height 8 is added. The garden contains three trees of heights 5, 7, 8.
  • Trees of height at most 7 are removed. The garden contains one tree of height 8.
  • A tree of height 3 is added. The garden contains two trees of heights 8, 3.

Sample Input 2

12
2 256601193
1 85138616
1 202564041
2 276477192
1 55551662
1 170271057
2 754166580
1 854388209
1 772036624
2 651124113
1 301137866
2 290875185

Sample Output 2

0
1
2
0
1
2
0
1
2
2
3
3