Bus Seat Allotment

Problem Preview

"### Problem There are infinite seats in a bus. There are $n$ people in a queue waiting to board the bus, and each wants to board and sit as seat $arr[i]$. It is given that the seat desired by each person is between $1$ and $n$. The allotment is done in the following manner: * If the seat desired by the person in the front of the queue is empty, they are allotted that seat and removed from the queue. * If the seat desired by the person in the front of the queue is occupied, the seat number desired by them is incremented by $1$ and they are pushed to the end of the queue. Find the final seat number allotted to each person in the queue. There are at most $10^5$ people in the queue."