Hello Codeforces community,
I've been working on a problem involving queue dynamics and chair allocation, and I'm seeking your expertise to find an efficient solution that fits within tight constraints.
Problem Statement: Description: You are given a queue of n people, numbered from 1 to n. Each person i has an initial preferred chair number Pi, which is a positive integer. There is an infinite number of chairs, labelled with positive integers starting from 1.
The queue operates under the following rules: Queue Processing: People are processed in the order they appear in the queue.
Chair Allocation Process: When a person reaches the front of the queue, they attempt to sit on their current preferred chair Pi.
If the chair Pi is unoccupied: They sit on chair Pi and leave the queue.
If the chair Pi is already occupied: They are sent to the end of the queue and their preferred chair number increases by 1. They will attempt to sit on this new preferred chair when they reach the front of the queue again.
This process continues until all people have been allocated a chair.
Objective: Determine the chair number allocated to each person, in the order of their original positions in the queue (from person 1 to person n).
Input Format: The first line contains an integer n (1 <= n <= 10^5), the number of people in the queue. The second line contains n space-separated positive integers P1, P2, ..., Pn. (1 <= Pi <= n), where Pi is the initial preferred chair number of the i-th person.
Output: n space-separated integers, where the i-th integer represents the chair number allocated to the i-th person.