codeforces#P1208D. Restore Permutation

    ID: 30415 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>binary searchdata structuresgreedyimplementation*1900

Restore Permutation

Description

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

There is a hidden permutation of length nn.

For each index ii, you are given sis_{i}, which equals to the sum of all pjp_{j} such that j<ij < i and pj<pip_{j} < p_{i}. In other words, sis_i is the sum of elements before the ii-th element that are smaller than the ii-th element.

Your task is to restore the permutation.

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

The second line contains nn integers s1,s2,,sns_{1}, s_{2}, \ldots, s_{n} (0sin(n1)20 \le s_{i} \le \frac{n(n-1)}{2}).

It is guaranteed that the array ss corresponds to a valid permutation of length nn.

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

Input

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

The second line contains nn integers s1,s2,,sns_{1}, s_{2}, \ldots, s_{n} (0sin(n1)20 \le s_{i} \le \frac{n(n-1)}{2}).

It is guaranteed that the array ss corresponds to a valid permutation of length nn.

Output

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

Samples

输入数据 1

3
0 0 0

输出数据 1

3 2 1

输入数据 2

2
0 1

输出数据 2

1 2

输入数据 3

5
0 1 1 1 10

输出数据 3

1 4 3 2 5

Note

In the first example for each ii there is no index jj satisfying both conditions, hence sis_i are always 00.

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

In the third example for i=2,3,4i = 2, 3, 4 only j=1j = 1 satisfies the conditions, so s2=s3=s4=1s_2 = s_3 = s_4 = 1. For i=5i = 5 all j=1,2,3,4j = 1, 2, 3, 4 are possible, so s5=p1+p2+p3+p4=10s_5 = p_1 + p_2 + p_3 + p_4 = 10.