Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Restore Permutation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAn array of integers $$$p_{1},p_{2}, \ldots,p_{n}$$$ is called a permutation if it contains each number from $$$1$$$ to $$$n$$$ exactly once. For example, the following arrays are permutations: $$$[3,1,2], [1], [1,2,3,4,5]$$$ and $$$[4,3,1,2]$$$. The following arrays are not permutations: $$$[2], [1,1], [2,3,4]$$$.

There is a hidden permutation of length $$$n$$$.

For each index $$$i$$$, you are given $$$s_{i}$$$, which equals to the sum of all $$$p_{j}$$$ such that $$$j < i$$$ and $$$p_{j} < p_{i}$$$. In other words, $$$s_i$$$ is the sum of elements before the $$$i$$$-th element that are smaller than the $$$i$$$-th element.

Your task is to restore the permutation.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the size of the permutation.

The second line contains $$$n$$$ integers $$$s_{1}, s_{2}, \ldots, s_{n}$$$ ($$$0 \le s_{i} \le \frac{n(n-1)}{2}$$$).

It is guaranteed that the array $$$s$$$ corresponds to a valid permutation of length $$$n$$$.

Output

Print $$$n$$$ integers $$$p_{1}, p_{2}, \ldots, p_{n}$$$ — the elements of the restored permutation. We can show that the answer is always unique.

Examples

Input

3 0 0 0

Output

3 2 1

Input

2 0 1

Output

1 2

Input

5 0 1 1 1 10

Output

1 4 3 2 5

Note

In the first example for each $$$i$$$ there is no index $$$j$$$ satisfying both conditions, hence $$$s_i$$$ are always $$$0$$$.

In the second example for $$$i = 2$$$ it happens that $$$j = 1$$$ satisfies the conditions, so $$$s_2 = p_1$$$.

In the third example for $$$i = 2, 3, 4$$$ only $$$j = 1$$$ satisfies the conditions, so $$$s_2 = s_3 = s_4 = 1$$$. For $$$i = 5$$$ all $$$j = 1, 2, 3, 4$$$ are possible, so $$$s_5 = p_1 + p_2 + p_3 + p_4 = 10$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 12:56:10 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|