Vasya has written some permutation 𝑝1,𝑝2,…,𝑝𝑛 of integers from 1 to 𝑛, so for all 1≤𝑖≤𝑛 it is true that 1≤𝑝𝑖≤𝑛 and all 𝑝1,𝑝2,…,𝑝𝑛 are different. After that he wrote 𝑛 numbers 𝑛𝑒𝑥𝑡1,𝑛𝑒𝑥𝑡2,…,𝑛𝑒𝑥𝑡𝑛. The number 𝑛𝑒𝑥𝑡𝑖 is equal to the minimal index 𝑖<𝑗≤𝑛, such that 𝑝𝑗>𝑝𝑖. If there is no such 𝑗 let's let's define as 𝑛𝑒𝑥𝑡𝑖=𝑛+1.

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values 𝑛𝑒𝑥𝑡𝑖 are completely lost! If for some 𝑖 the value 𝑛𝑒𝑥𝑡𝑖 is lost, let's say that 𝑛𝑒𝑥𝑡𝑖=−1.

You are given numbers 𝑛𝑒𝑥𝑡1,𝑛𝑒𝑥𝑡2,…,𝑛𝑒𝑥𝑡𝑛 (maybe some of them are equal to −1). Help Vasya to find such permutation 𝑝1,𝑝2,…,𝑝𝑛 of integers from 1 to 𝑛, that he can write it to the notebook and all numbers 𝑛𝑒𝑥𝑡𝑖, which are not equal to −1, will be correct.

#### 链接 🔗

「CodeForces 1158C」Permutation recovery

#### 代码

const int N = 2e6+10;
ll a[N],ls[N],rs[N],tot,id[N],rt,d[N],ans[N],n,num;
V G[N];
void build(ll &p,ll l,ll r)
{
p = ++tot; a[p] =  d[p] = 0; G[p].clear();
if(l==r)
{
a[p] = l, id[l] = p;
return;
}
build(ls[p],l,mid);
build(rs[p],mid+1,r);
G[p].pb(ls[p]); G[p].pb(rs[p]);
d[ls[p]]++;d[rs[p]]++;
}
ll change(ll p,ll l,ll r,ll x,ll y,ll v)
{
if(x > y) return 0;
if(x <= l && r <= y) return G[v].pb(p),d[p]++;
if(x <= mid) change(ls[p],l,mid,x,y,v);
if(y > mid) change(rs[p],mid+1,r,x,y,v);
}
int main()
{
//    __IN;__OUT;
ll t;RLL(t);
while(t--)
{
RLL(n); tot = 0; num = n;
build(rt,1,n);
FOR(i,1,n)
{
ll x;RLL(x);
if(x!=-1)
{
if(i+1 <= x-1) change(rt,1,n,i+1,x-1,id[i]);
if(x <= n)
G[id[x]].pb(id[i]),d[id[i]]++;
}
}
queue<ll> que;

FOR(i,1,tot) if(!d[i])que.push(i);
while(!que.empty())
{
ll x = que.front(); que.pop();
if(a[x]) ans[a[x]] = num--;
for(auto v:G[x])
{
--d[v];
if(!d[v]) que.push(v);
}
}
if(num) PS("-1");
else
{
FOR(i,1,n) PLP(ans[i]);
PN();
}
}
return 0;
}