分数: 300 点
问题陈述
高桥正在管理他花园里的树木数量。最初,花园里没有树木。
Q 查询按顺序给出。每个查询都是以下两种类型之一。处理每个查询后,立即输出花园中当前的树木数量。
1 h: 添加一棵新树的高度 h 到花园。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
\text{query}_i,代表 i-th 查询,是以下两种类型之一:
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.
- 一棵高树 添加了 7 。花园里有两棵高大的树 添加了 5, 7.
- 一棵高树 添加了 8 。花园里有三棵高树 5, 7, 8.
- 树的高度最高 7 被删除。花园里有一棵高大的树 8.
- 一棵高树 添加了 3 。花园里有两棵高大的树 添加了 8, 3.
示例输入 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