D. Restore Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

An array of integers p1,p2,…,pnp1,p2,…,pn 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 sisi, which equals to the sum of all pjpj such that j<ij<i and pj<pipj<pi. In other words, sisi 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.

Input

The first line contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the size of the permutation.

The second line contains nn integers s1,s2,…,sns1,s2,…,sn (0≤si≤n(n−1)20≤si≤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,…,pnp1,p2,…,pn — the elements of the restored permutation. We can show that the answer is always unique.

Examples

input

Copy

30 0 0

output

Copy

3 2 1

input

Copy

20 1

output

Copy

1 2

input

Copy

50 1 1 1 10

output

Copy

1 4 3 2 5

Note

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

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

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

 

 题目链接：

题解：首先我们需要建立一个权值线段树，节点的权值分别是1~n，然后我就只需要逆序遍历si数组，找到大于s[i] + 1的数，这个数就是当前位置的值。注意的是，如果我们找到了那个数，就要将那个位置的权值赋为0，表示该数已经用过了。

 

#include 
     
      #include 
      
       using namespace std;const int maxn = 2e5+7;typedef long long ll;ll s[maxn], ans[maxn], tree[maxn << 2];void update(int root, int l, int r, int pos, ll val) {    if(l == r) {        tree[root]= val;        return;    }    int mid = (l + r) >> 1;    if(pos <= mid) {        update(root << 1, l, mid, pos, val);    } else {        update(root << 1 | 1, mid + 1, r, pos, val);    }    tree[root] = tree[root << 1] + tree[root << 1 | 1];}int query(int root, int l, int r, ll val) {    if(l == r) {        return tree[root];    }    int mid = (l + r) >> 1;    if(tree[root << 1] >= val) {        return query(root << 1, l, mid, val);    } else {        return query(root << 1 | 1, mid + 1, r, val - tree[root << 1]);    }}int main() {    int n;    scanf("%d", &n);    for(int i = 1; i <= n; i++) {        scanf("%I64d", &s[i]);        update(1, 1, n, i, i * 1LL);    //建立一颗权值线段树    }    for(int i = n; i >= 1; i--) {        ans[i] = query(1, 1, n, s[i] + 1LL);    //找到大于si + 1的这个数        update(1, 1, n, ans[i], 0LL);    //权值赋0    }    for(int i = 1; i <= n; i++) {        printf("%I64d ", ans[i]);    }    return 0;    }