The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 162 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Roadside Trees

time limit per test

5 secondsmemory limit per test

256 megabytesinput

stdinoutput

stdoutSquirrel 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:

- Plant a tree of height
*h*at position*p*. - 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.

Input

The first line contains two integers: *n* and *m* (1 ≤ *n* ≤ 10^{5}; 1 ≤ *m* ≤ 2·10^{5}) — 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.

Output

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

Examples

Input

4 6

1 1 1

1 4 4

1 3 4

2 2

1 2 8

2 3

Output

1

2

3

2

2

2

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2024 20:44:06 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|