松鼠利斯喜欢坚果。利斯要求你种植一些坚果树。
沿街道有n个位置(从西到东编号为1到n)可以种植一棵树。树木每月生长一米。在每个月初,您应该处理一个查询。查询是以下类型之一:
1. 在位置 p 处种植一棵高度为 h 的树。
2. 从西边砍掉第 x 棵现存(未砍伐)树(其中 x 的索引为 1)。当我们砍伐树木时,它会掉落并占据其原来所在位置的所有可用位置。所以这个位置不能再种树了。
处理完每个查询后,您应该打印最长递增子序列的长度。如果集合中树的高度严格地从西向东递增(例如,集合中最西边的树必须是集合中最矮的树),则现有树的子集称为递增子序列。递增子序列的长度就是其中的树数。
请注意,Liss 不喜欢具有相同高度的树,因此可以保证任何时候都没有两棵树具有完全相同的高度。
输入
第一行包含两个整数:n 和 m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2·105) — 位置数和查询数。
接下来的m行包含以下格式的查询信息:
- 如果第 i 个查询是类型 1,则第 i 行包含三个整数:1、pi 和 hi(1 ≤ pi ≤ n, 1 ≤ hi ≤ 10),其中 pi 是新树的位置,hi 是新树的初始高度。
- 如果第 i 个查询是类型 2,则第 i 行包含两个整数:2 和 xi (1 ≤ xi ≤ 10),其中 xi 是我们要切割的树的索引。
保证输入正确,即
- 对于类型 1 查询,pi 将成对不同。
- 对于类型 2 查询,xi 将小于或等于当前树的数量。
- 任何时候都没有两棵树具有完全相同的高度。
在每一行中,整数之间用单个空格分隔。
输出
打印 m 个整数 — 每次查询后最长递增子序列的长度。用空格分隔数字。
示例
输入 #1
4 6 1 1 1 1 4 4 1 3 4 2 2 1 2 8 2 3
输出 #1
1 2 3 2 2 2
注意
每次查询后您可以在以下动画中看到街道状态:
如果您的浏览器不支持动画 png,请在此处查看 gif 版本:http://212.193.37.254/codeforces/images/162/roadtree.gif