Reconstruct the Queue
Time limit1sMemory limit128 MB
Given each arrival's insertion spot in a growing queue, compute every person's final position at dispersal.
- Level
Medium5 of 10
- Topics
- Segment tree
- Solved
- No attempts yet
Problem
The construction worker Adrian has little to do today, so he is collecting material for his study of shop queues.
Adrian watches the queue in front of a nearby shop and, for each person who arrives in turn, writes down the position in the queue that person took. At the start of the day the queue was empty. A new arrival did not necessarily stand at the very back: by arranging things with someone, paying someone, handing over something, or in some other way, a person could cut into any position in the queue. Once someone joined the queue they never left it, until noon, when it turned out the shop would not open that day and everyone dispersed.
Using only his notes, Adrian wonders whether the arrangement of the queue just before everyone dispersed can be reconstructed.
Input
The first line contains the number of test sets (). The test sets then follow one after another.
The first line of each set contains a natural number (), the number of people who joined the queue between morning and noon. The second line contains integers (, for ).
If is , the -th person stood at the very front of the queue. Otherwise the -th person stood directly behind the person who, at the moment they arrived, was the -th person counting from the front of the queue.
Output
For each set, print on its own line integers separated by single spaces. The -th integer must be the final position of the person who joined the queue -th. The person at the front of the queue has position , the next has position , and so on.