ORDERS  Ordering the Soldiers
As you are probably well aware, in Byteland it is always the military officer's main worry to order his soldiers on parade correctly. In Bitland ordering soldiers is not really such a problem. If a platoon consists of n men, all of them have different rank (from 1  lowest to n  highest) and on parade they should be lined up from left to right in increasing order of rank.
Sounds simple, doesn't it? Well, Msgt Johnny thought the same, until one day he was faced with a new command. He soon discovered that his elite commandos preferred to do the fighting, and leave the thinking to their superiors. So, when at the first rollcall the soldiers lined up in fairly random order it was not because of their lack of discipline, but simply because they couldn't work out how to form a line in correct order of ranks. Msgt Johnny was not at all amused, particularly as he soon found that none of the soldiers even remembered his own rank. Over the years of service every soldier had only learned which of the other soldiers were his superiors. But Msgt Johnny was not a man to give up easily when faced with a true military challenge. After a moment's thought a solution of brilliant simplicity struck him and he issued the following order: "men, starting from the left, one by one, do: (step forward; go left until there is no superior to the left of you; get back in line).". This did indeed get the men sorted in a few minutes. The problem was solved... for the time being.
The next day, the soldiers came in exactly the same order as the day before, and had to be rearranged using the same method. History repeated. After some weeks, Msgt Johnny managed to force each of his soldiers to remember how many men he passed when going left, and thus make the sorting process even faster.
If you know how many positions each man has to walk to the left, can you try to find out what order of ranks the soldiers initially line up in?
Input
The first line of input contains an integer t<=50, the number of test cases. It is followed by t test cases, each consisting of 2 lines. The first line contains a single integer n (1<=n<=200000). The second line contains n space separated integers w_{i}, denoting how far the ith soldier in line must walk to the left when applying Msgt Johnny's algorithm.
Output
For each test case, output a single line consisting of n space separated integers  the ranks of the soldiers, given from left to right in their initial arrangement.
Example
Input: 2 3 0 1 0 5 0 1 2 0 1 Output: 2 1 3 3 2 1 5 4Warning: large Input/Output data, be careful with certain languages
hide comments
naimish007:
20191016 12:08:43
AC in one go. Use PBDS 

sherlock11:
20180614 17:05:45
start from right and figure out what will be the position of that soldier because position of that soldier can be affected by only those who are standing after him.........


amulyagaur:
20180302 14:44:32
Just 30 lines of code in c++ using policy based DS! 

shiv2111:
20180102 00:04:43
BIT 

anubhawiiitu:
20171226 20:23:29
This problem is similar to "counting inversion of array" problem using segment tree. Accepted in 0.34 s.


shloksingh10:
20170713 18:40:58
preequisite:


sonudoo:
20170702 13:53:40
The problem made me so confused that I was even confused about the fact whether the soldier movement were left from their perspective or from commander's perspective.... Finally I tried all combinations to get 3 1 2 as the answer to 0 1 1.. 

Karan Thakkar:
20160722 17:41:08
I submitted successfully with the time of 11.01 seconds without recursion, using for and while loops. How long does it take with recursion? 

romilpunetha:
20160616 04:51:29
why is 1 0 1 a test case _ 

minhthai:
20160203 03:12:21
ac with binary tree but this is hard though 
Added by:  adrian 
Date:  20041030 
Time limit:  13s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  DASM Programming League 2004, problemset 2 