codeforces#P1208D. Restore Permutation
Restore Permutation
Description
An array of integers is called a permutation if it contains each number from to exactly once. For example, the following arrays are permutations: and . The following arrays are not permutations: .
There is a hidden permutation of length .
For each index , you are given , which equals to the sum of all such that and . In other words, is the sum of elements before the -th element that are smaller than the -th element.
Your task is to restore the permutation.
The first line contains a single integer () — the size of the permutation.
The second line contains integers ().
It is guaranteed that the array corresponds to a valid permutation of length .
Print integers — the elements of the restored permutation. We can show that the answer is always unique.
Input
The first line contains a single integer () — the size of the permutation.
The second line contains integers ().
It is guaranteed that the array corresponds to a valid permutation of length .
Output
Print integers — the elements of the restored permutation. We can show that the answer is always unique.
Samples
Note
In the first example for each there is no index satisfying both conditions, hence are always .
In the second example for it happens that satisfies the conditions, so .
In the third example for only satisfies the conditions, so . For all are possible, so .