ABC 略
D
首先可以确定新序列单调不递减。在操作中，a[i]如果存在j>i&&a[j]<a[i]，那么a[i]一定会向后移动。我们从1~n依次往一个栈中加数，使这个栈单调，而被踢出的数则+1，等待新的加入。很明显就是单调栈。踢出的数我们随意加入可能会导致这些数多次加入，如果从小到大加入就能保证每个数最多加入一次，因为其他踢出的数肯定比这个数大。用单调队列维护。这样保证每个数最多加入两次，进入队列一次。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,a[N],stac[N],tot;
priority_queue<int> q;
void init()
{tot=0;while(q.size()) q.pop();
}
void solve()
{ cin>>n;init();for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){while(stac[tot]>a[i]){q.push(-(stac[tot]+1));tot--;}stac[++tot]=a[i];}while(q.size()){int x=-q.top();q.pop();while(stac[tot]>x){q.push(-(stac[tot]+1));tot--;}stac[++tot]=x;}for(int i=1;i<=n;i++)cout<<stac[i]<<" ";cout<<endl;
}
signed main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--) solve();
}
