Assume that you are the manager of Kitty Hotel, where they provide accommodation for cats on vacation. The hotel has n rooms in total, labelled from 1 to n for convenience.
There is exactly 1 room in each floor, with the ith room on the ith floor. However, there is no booking system and the manager only manages the total number of cats that enter the hotel, making sure it is less than or equal to the number of rooms the hotel has.
Each cat that enters the hotel will take the lift to a certain floor, x. If that floor is vacant, it will occupy that floor. However, if that floor isn't vacant, it will walk down the floors until it finds a floor that is vacant and occupy it. In the event that a cat reaches floor 1 and the room there is still occupied, it will then take the lift up to the nth floor and continue walking downwards until it encounters a vacant floor.
Given the number of cats, c and the floor each cat takes the lift to, determine which floor does it eventually occupy, provided that they arrive in chronological order.
The first line of input will consists of 2 integers, n followed by c
Subsequent c lines will consist of 1 integer each, which is the floor the cat took the lift to.
For each cat, output a single integer indicating the floor it eventually occupies.
Subtask 1 (30%): 0 ≤ n, c ≤ 1000
Subtask 2 (30%): 0 ≤ n, c ≤ 200000
Subtask 3 (40%): 0 ≤ n ≤ 10000000, 0 ≤ c ≤ 2000000