Problem 2: Find the Permutation, (Tanmoy Chakraborty, Indraneel Mukherjee, CMI)
A permutation of the numbers 1, ..., N is a rearrangment of these numbers. For example
2 4 5 1 7 6 3 8
is a permutation of 1,2, ..., 8. Of course,
1 2 3 4 5 6 7 8
is also a permutation of 1, 2, ..., 8.
Associated with each permutation of N is a special sequence of positive integers of length N called its inversion sequence. The ith element of this sequence is the number of numbers j that are strictly less than i and appear to the right of i in this permutation. For the permutation
2 4 5 1 7 6 3 8
the inversion sequence is
0 1 0 2 2 1 2 0
The 2nd element is 1 because 1 is strictly less than 2 and it appears to the right of 2 in this permutation. Similarly, the 5th element is 2 since 1 and 3 are strictly less than 5 but appear to the right of 5 in this permutation and so on.
As another example, the inversion sequence of the permutation
8 7 6 5 4 3 2 1
is
0 1 2 3 4 5 6 7
In this problem, you will be given the inversion sequence of some permutation. Your task is to reconstruct the permutation from this sequence.
Input format
The first line consists of a single integer N. The following line contains N integers, describing an inversion sequence.
Output format
A single line with N integers describing a permutation of 1, 2, ..., N whose inversion sequence is the given input sequence.
Test Data:
You may assume that N ≤ 100000. You may further assume that in at least 50% of the inputs N ≤ 8000.
Example:
Here are sample inputs and outputs corresponding to the example discussed above.
Sample Input 1
8 0 1 0 2 2 1 2 0
Sample Output 1
2 4 5 1 7 6 3 8
Sample Input 2
8 0 1 2 3 4 5 6 7
Sample Output 2
8 7 6 5 4 3 2 1