Linear network#10455
A linear network consisting of computers was installed in a big data processing center. All computers are numbered consecutively with integers from to . There is a direct connection between any two computers with consecutive numbers. Clearly, in such a network, data can be exchanged between any two computers, either directly or through intermediate ones. However, due to the high workload, some computers may fail. In such cases, connections between certain computers are disrupted, making data transfer between them impossible.
Your task is to determine the current number of groups in the network. A group is defined as the largest subset of active computers where any two computers are connected either directly or through other computers. A group can also consist of a single computer.
You need to answer queries. Each query either reports the failure of one of the computers or requests the current number of groups.
The first line contains two integers n~(1 \le n \le 10^9) and q~(1 \le q \le 10^5) — the number of computers and the number of queries, respectively. Each of the following lines represents a query.
Each query starts with an integer (T = 1, 2), indicating its type. If T = 1, it is followed by an integer L~(1 \le L \le n), which is the number of the computer that has failed.
A query of type T = 1 indicates that the computer numbered has failed.
A query of type T = 2 requests the current number of groups in the network.
For each query of the second type (T = 2), print the current number of groups in the network on a separate line.
— Initial state of the network. The number of groups is .
— The state of the network after the failure of the computer number . Number of groups — .
— The state of the network after the failure of the computer number . Number of groups — .
— The state of the network after the failure of the computer number . Number of groups — .
The requests for computer failure may be repeated.
Example 1