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<iand 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
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 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.
一开始p中最右边的0的位置对应着原序列中的1，我们确定了1的位置，将1后面的每个数减1，p中最右边的0的位置就对应着原序列中的2，我们就能确定原序列中2的位置，以此类推我们就能得出整个原序列。用数据结构维护一下区间最小值和区间更新就行了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iostream>
#include<time.h>
using namespace std;
typedef long long slong;
const int maxn=200005;
const double exc=1e-7;
const long long inf=1e15;
int ans[maxn];
struct value
{
long long val;
int index;
};
struct point
{
long long f;
value w;
}tree[maxn<<2];
int cnt;
void up(int k)
{
if(tree[k*2].w.val<tree[k*2+1].w.val)
tree[k].w=tree[k*2].w;
else tree[k].w=tree[k*2+1].w;
}
void build(int l,int r,int k)
{
tree[k].f=0;
tree[k].w.val=inf;
if(l==r)
{
tree[k].w.index=++cnt;
scanf("%lld",&tree[k].w.val);
return;
}
int bet=(l+r)/2;
build(l,bet,k*2);
build(bet+1,r,k*2+1);
up(k);
}
void down(int k)
{
tree[k*2].w.val-=tree[k].f;
tree[k*2+1].w.val-=tree[k].f;
tree[k*2].f+=tree[k].f;
tree[k*2+1].f+=tree[k].f;
tree[k].f=0;
}
void change(int l,int r,int k,long long val,int ll,int rr)
{
if(ll<=l&&rr>=r)
{
tree[k].w.val-=val;
tree[k].f+=val;
return;
}
if(tree[k].f) down(k);
int bet=(l+r)/2;
if(ll<=bet) change(l,bet,k*2,val,ll,rr);
if(rr>bet) change(bet+1,r,k*2+1,val,ll,rr);
up(k);
}
void pointchange(int l,int r,int k,long long val,int poi)
{
if(l==r)
{
tree[k].w.val=val;
return;
}
if(tree[k].f) down(k);
int bet=(l+r)/2;
if(poi<=bet) pointchange(l,bet,k*2,val,poi);
else pointchange(bet+1,r,k*2+1,val,poi);
up(k);
}
int main()
{
int n;
scanf("%d",&n);
build(1,n,1);
for(int i=1;i<=n;i++)
{
value a=tree[1].w;
ans[a.index]=i;
pointchange(1,n,1,inf,a.index);
change(1,n,1,i,a.index,n);
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
printf("\n");
return 0;
}