Problem Description
It is a fine and sunny day and Rar the Cat decides to go on a fishing trip. (Yes, it sounds like a chinese composition translated into English.)
He has several locations to choose from when going on a fishing trip. He can either choose to fish at the sea shore, at the river, at Underwater World, at Sea Aquarium or even at Adventure Cove! Out of these locations, he prefers to fish by the river and his favourite river is called the Riverline.
Rar the Cat prefers to fish by the Riverline because the water is clean and clear. Furthermore, Riverline looks like a straight line on the map, which is where it got its name from. Due to the pre-dominant wind always blowing in the same direction, one bank (or side) of Riverline is filled with swamps, leaving only one bank of Riverline for fishing. Since Riverline is N metres long, it can also only hold N cats fishing at the same time, with one cat taking up 1 metre of the river bank to fish. This effectively segments the river into N fishing spots labelled 1 to N for cats to fish. Each fishing spot can only be occupied by one cat at any point in time.
Many cats prefer to go to Riverline to fish precisely because they are anti-social. At Riverline, they do not have to face other cats opposite the bank while fishing (it is not possible to fish on the opposite bank), which reduces awkwardness. Due to this, they also tend to sit as far away from each other as possible. Each cat that arrives will choose a fishing spot that maximises the minimum distance from other cats on the riverbank. In the event that there is more than one different fishing spot that maximises the minimum distance from other cats, the arriving cat will always choose the fishing spot with the lowest label as it requires the least amount of walking from the entrance of the Riverline designated fishing zone (which is directly before fishing spot 1). When Riverline is empty, the next cat that arrive will always occupy fishing spot 1, the fishing spot nearest to the entrance. Cats are always lazy.
Of course, Rar the Cat does not fish all day and might leave when he is done fishing. The same can be said for other cats. Hence, which fishing spot the next cat will choose can be different for different occasions. Rar the Cat bets that it is impossible for you to predict which fishing spot a cat will end at given a list of cats that arrive and leave Riverline, given in chronological order. Now, you want to prove him wrong using your programming skills.
Input and Output
Rar the Cat has kindly provided you with nicely formatted input.
The first 2 integers of the input would be N and M, which denote the length of Riverline in metres and the number of events that happen on Riverline respectively. There are 2 types of event, a cat arriving at Riverline and when a cat leaves Riverline. For convenience sake, the ith cat that arrives at Riverline will be given an identification number of i.
The next M lines of input will consist of an event each. Each event starts with a number 0 or 1, denoting whether it is a cat arriving at Riverline or leaving Riverline, respectively. If the event has a number 0, you are to output the label of the fishing spot of which the cat would be fishing at. If the event has a number 1, it will be followed by a second integer, x, which denotes that cat with identification number of x is now leaving Riverline. You are not to output anything for type 1 events.
It is guaranteed that the number of cats fishing at Riverline will not exceed N at any point in time.
Limits
Subtask 1 (24%): 1 ≤ N, M ≤ 200.
Subtask 2 (11%): 1 ≤ N, M ≤ 2000.
Subtask 3 (31%): 1 ≤ N ≤ 109, 1 ≤ M ≤ 2000.
Subtask 4 (34%): 1 ≤ N ≤ 109, 1 ≤ M ≤ 200000.
Sample Input 1
10 12
0
0
0
0
1 2
1 3
0
1 1
0
0
1 7
0
Sample Output 1
1
10
5
3
10
6
1
1
The first cat will fish at fishing spot 1.
The second cat will fish at fishing spot 10 as this maximises the distance from the cat at fishing spot 1.
To maximise the distance from other cats, cat 3 can fish at fishing spot 5 or 6 as this will mean a distance of 4 metres with the nearest cat. Since fishing spot 5 is nearer to the entrance, cat 3 will fish at fishing spot 5.
To maximise the distance from other cats, cat 4 can fish at fishing spot 3, 7 or 8 as this will mean a distance of 2 metres with the nearest cat. Since fishing spot 3 is nearer to the entrance, cat 4 will fish at fishing spot 3.
Cat 2 and 3 now leaves. This leaves cat 1 at fishing spot 1, and cat 4 at fishing spot 3.
Cat 5 enters Riverline and will fish at fishing spot 10 as this maximises the distance from other cats.
Cat 1 now leaves. This leaves cat 4 at fishing spot 3 and cat 5 at fishing spot 10.
Cat 6 enters Riverline and settles at fishing spot 6.
Cat 7 enters Riverline and settles at fishing spot 1.
Cat 7 leaves Riverline, leaving cat 4 at fishing spot 3, cat 6 at fishing spot 6, cat 5 at fishing spot 10.
Cat 8 enters Riverline and will settle at fishing spot 1, effectively replacing cat 7.
Sample Input 2
10 10
0
0
0
0
0
0
0
0
0
0
Sample Output 2
1
10
5
3
7
2
4
6
8
9
Acknowledgements
This problem is adapted from 20th Central European Olympiad in Informatics (2013) Day 1 Task Tram and CodeForces Problem Hanger (74D).