ll@n,@p[n],s[n+1]{},v[];
rep(i,n){
	v[p[i]]=i;
}
rep(a,1,n+1){
	ll i=v[a];
	if(!s[i]){
		ll j=i+1;
		while(s[j]){
			j=s[j];
		}
		ll k=i+1;
		while(s[k]){
			(s[k],k)=(j,s[k]);
		}
		if(j<n){
			wtSp(a,p[j]);
			s[i]=j;
			s[j]=j+1;
		}
	}
}