Indian National Olympiad in Informatics

Related:

Online Programming Contest, 4-5 June, 2005

IARCS home > OLYMPIAD

Advanced Division

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

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