eolymp
Competitions

2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8

Linear network

A linear network of n computers was installed in the big data center. All computers are numbered with integers sequentially from 1 to n. There is a direct communication between computers with neighbouring numbers. It is clear that in such a network it is possible to directly or indirectly exchange data between any two computers. However, due to the intensity of the operations, some computers sometimes fail. In such cases, the communication between some computers is interrupted and data transfer becomes impossible.

You are asked to find out the number of groups in the network at the moment. A group is the maximum number of active computers where any two computers from the same group have communication with each other. Also, a group can consist of only one computer.

You need to answer q queries. In each of the queries, either the number of the computer that has just failed is given, or it is necessary to count the number of groups.

For a better understanding of the problem, below is an explanation for the example.

Input

The first line contains two integers n and q. The following q lines contain queries.

Each query starts with a number T indicating the type of request. T = 1 is always followed by the number L of the failed computer.

Output

For each query of the 2-nd type, it is necessary to print the number of groups in the network at the current moment in a separate line.

Restrictions

  • 1n109
  • 1q105
  • T = 1, 2
  • 1Ln

Subtasks

This problem consists of 3 subtasks:

SubtaskRestrictionsPoints
0Example0 points
1n104, q10014 points
2n10537 points
3No additional restrictions49 points

Explanation

1 2 3 4 -- Initial state of the network. The number of groups is 1.

1 x 3 4 -- The state of the network after the failure of the computer number 2. Number of groups - 2.

1 x 3 x -- The state of the network after the failure of the computer number 4. Number of groups - 2.

1 x 3 x -- The state of the network after the failure of the computer number 2. Number of groups - 2.

Note: the requests for computer failure may be repeated.
Time limit 1 second
Memory limit 256 MiB
Input example #1
4 6
1 2
2
1 4
2
1 2
2
Output example #1
2
2
2
Source 2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8