CF264E.Roadside Trees

Squirrel Liss loves nuts. Liss asks you to plant some nut trees.

There are n positions (numbered 1 to n from west to east) to plant a tree along a street. Trees grow one meter per month. At the beginning of each month you should process one query. The query is one of the following types:

1. Plant a tree of height h at position p.
2. Cut down the x-th existent (not cut) tree from the west (where x is 1-indexed). When we cut the tree it drops down and takes all the available place at the position where it has stood. So no tree can be planted at this position anymore.

After processing each query, you should print the length of the longest increasing subsequence. A subset of existent trees is called an increasing subsequence if the height of the trees in the set is strictly increasing from west to east (for example, the westmost tree in the set must be the shortest in the set). The length of the increasing subsequence is the number of trees in it.

Note that Liss don't like the trees with the same heights, so it is guaranteed that at any time no two trees have the exactly same heights.

松鼠Liss热爱坚果。Liss请你种植一些坚果树。

街道上共有 $n$ 个位置（从西向东编号为 $1$ 到 $n$）可用于种树。树木每月生长 $1$ 米。在每个月初，你需要处理一个查询。该查询属于以下两种类型之一：

1. 在位置 $p$ 处种植一棵高度为 $h$ 的树。
2. 从西向东数第 $x$ 棵现存（未被砍伐）的树（其中 $x$ 为从 $1$ 开始计数的索引）被砍倒。当一棵树被砍倒时，它会倒下并占据其原本所在位置的全部空间。因此此后该位置不能再种植任何树。

每次查询处理完毕后，你应输出当前最长递增子序列的长度。所谓“现存树的一个递增子序列”，是指其中各棵树的高度从西向东严格递增（例如：该子序列中最西边的树必须是其中最矮的）。该递增子序列的长度即为其所含树的数量。

注意：Liss不喜欢高度相同的树，因此题目保证在任意时刻不存在两棵高度完全相同的树。

The first line contains two integers: n and m (1  ≤ n ≤ 105; 1 ≤ m ≤ 2·105) — the number of positions and the number of queries.

Next m lines contains the information of queries by following formats:

• If the i-th query is type 1, the i-th line contains three integers: 1, p__i, and h__i (1 ≤ p__i ≤ n, 1 ≤ h__i ≤ 10), where p__i is the position of the new tree and h__i is the initial height of the new tree.
• If the i-th query is type 2, the i-th line contains two integers: 2 and x__i (1 ≤ x__i ≤ 10), where the x__i is the index of the tree we want to cut.

The input is guaranteed to be correct, i.e.,

• For type 1 queries, p__i will be pairwise distinct.
• For type 2 queries, x__i will be less than or equal to the current number of trees.
• At any time no two trees have the exactly same heights.

In each line integers are separated by single spaces.

第一行包含两个整数：$n$ 和 $m$（$1 \leq n \leq 10^5$；$1 \leq m \leq 2 \cdot 10^5$）——分别表示位置数量和查询次数。

接下来的 $m$ 行描述各次查询，格式如下：

• 若第 $i$ 次查询为类型 1，则第 $i$ 行包含三个整数：1、$p_i$ 和 $h_i$（$1 \leq p_i \leq n$，$1 \leq h_i \leq 10$），其中 $p_i$ 表示新树的位置，$h_i$ 表示新树的初始高度。
• 若第 $i$ 次查询为类型 2，则第 $i$ 行包含两个整数：2 和 $x_i$（$1 \leq x_i \leq 10$），其中 $x_i$ 表示我们想要砍伐的树的编号。

输入数据保证合法，即：

• 对于类型 1 的查询，所有 $p_i$ 互不相同；
• 对于类型 2 的查询，$x_i$ 不超过当前已有的树的总数；
• 在任意时刻，不存在两棵树具有完全相同的高度。

每行中的整数以单个空格分隔。

Print m integers — the length of the longest increasing subsequence after each query. Separate the numbers by whitespaces.

输出 m 个整数——每次查询后最长递增子序列的长度。各数字之间用空格分隔。

States of street after each query you can see on the following animation:

If your browser doesn't support animation png, please see the gif version here: http://212.193.37.254/codeforces/images/162/roadtree.gif

每次查询后街道的状态如下动画所示：

如果您的浏览器不支持动画 PNG 格式，请点击此处查看 GIF 版本：http://212.193.37.254/codeforces/images/162/roadtree.gif