玄关FHQ_treap求调喵qwq

#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
mt19937 treap_rand(0x0d000721);
const int MAXN=1e5+10;
struct FHQ_Treap{
#define LC tr[p].lc
#define RC tr[p].rc
	struct Node{
		int lc,rc;
		int val,key;
		int siz,tag;
		int minv;
	};
	Node tr[MAXN];
	int root,tot;
	FHQ_Treap(){
		tr[0].minv=INT32_MAX;
	}
	inline int newNode(int x){
		tr[++tot]={0,0,x,(int)treap_rand(),1,0,x};
		return tot;
	}
	inline void push_up(int p){
		tr[p].siz=tr[LC].siz+tr[RC].siz+1;
		tr[p].minv=min(tr[p].val,min(tr[LC].minv,tr[RC].minv));
	}
	inline void push_down(int p){
		if(tr[p].tag){
			swap(LC,RC);
			tr[LC].tag^=1;
			tr[RC].tag^=1;
			tr[p].tag=0;
		}
	}
	int merge(int x,int y){
		if(!x||!y){
			return x+y;
		}
		if(tr[x].key<tr[y].key){
			push_down(x);
			tr[x].rc=merge(tr[x].rc,y);
			push_up(x);
			return x;
		}
		else{
			push_down(y);
			tr[y].lc=merge(x,tr[y].lc);
			push_up(y);
			return y;
		}
	}
	void split(int p,int k,int &x,int &y){
		if(!p){
			x=y=0;
			return ;
		}
		push_down(p);
		if(tr[LC].siz<k){
			x=p;
			split(RC,k-tr[LC].siz-1,RC,y);
		}
		else{
			y=p;
			split(LC,k,x,LC);
		}
		push_up(p);
	}
	void reverse(int l,int r){
		int x,y,z;
		split(root,r,y,z);
		split(y,l-1,x,y);
		tr[y].tag^=1;
		root=merge(merge(x,y),z);
	}
	int find_min(){
		int p=root,rk=0;
		while(tr[p].val!=tr[p].minv){
			push_down(p);
			if(tr[LC].minv==tr[p].minv){
				p=LC;
			}
			else{
				rk+=tr[LC].siz+1;
				p=RC;
			}
		}
		return rk+tr[LC].siz+1;
	}
	inline void pop_first(){
		int x,y;
		split(root,1,x,y);
		root=y;
	}
};
int n;
FHQ_Treap treap;
pair<int,int> a[MAXN];
int sorted[MAXN];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i){
		sorted[a[i].second]=i;
	}
	for(int i=1;i<=n;++i){
		treap.root=treap.merge(treap.root,treap.newNode(sorted[i]));
	}
	for(int i=1;i<=n;++i){
		int tmp=treap.find_min();
		cout<<tmp+i-1;
		if(i!=n){
			cout<<' ';
		}
		treap.reverse(1,tmp);
		treap.pop_first();
	}
	return 0;
}