This page is still under construction.

Parts of this page are still being built. What you see may change.

Reconstruct the Queue

Time limit1sMemory limit128 MB

Summary
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 ZZ (1≤Z≤101 \le Z \le 10). The test sets then follow one after another.

The first line of each set contains a natural number NN (1≤N≤1000001 \le N \le 100000), the number of people who joined the queue between morning and noon. The second line contains NN integers X1,X2,…,XNX_1, X_2, \dots, X_N (0≤Xi<i0 \le X_i < i, for 1≤i≤N1 \le i \le N).

If XiX_i is 00, the ii-th person stood at the very front of the queue. Otherwise the ii-th person stood directly behind the person who, at the moment they arrived, was the XiX_i-th person counting from the front of the queue.

Output

For each set, print on its own line NN integers separated by single spaces. The ii-th integer must be the final position of the person who joined the queue ii-th. The person at the front of the queue has position 11, the next has position 22, and so on.

Examples3

  1. Example 1

    Input
    2
    5
    0 0 0 0 0
    5
    0 1 2 3 4
    
    Expected output
    5 4 3 2 1
    1 2 3 4 5
    
  2. Example 2

    Input
    1
    1
    0
    
    Expected output
    1
    
  3. Example 3

    Input
    1
    4
    0 1 1 2
    
    Expected output
    1 4 2 3