RT。

#include<bits/stdc++.h>
#define N 100005
#define bh ((a[i]-1)/kc+1)
using namespace std;
int a[100005];
struct Pri{
	vector<int>a;
	int w=0;
	Pri(){
		a.push_back(0);
	}
	int find()
	{
		return a[1];
	}
	void pushx(int x)
	{
		if(x==1||a[x/2]<a[x]) return;
		swap(a[x/2],a[x]);
		pushx(x/2);
	}
	void push(int x)
	{
		a.push_back(x);
		w++;
		pushx(w);
	}
	void popx(int x)
	{
		if(x*2>w) return;
		int now=2*x;
		if(x*2+1<=w)
		now=a[x*2]<a[x*2+1]?x*2:x*2+1;
		if(a[x]>a[now])
		{
			swap(a[x],a[now]);
			popx(now);
		}
	}
	void pop()
	{
		swap(a[1],a[w--]);
		popx(1); 
		a.pop_back();
	}
}q[32500];
int main()
{
	int n,kc=sqrt(1000000000);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		q[bh].push(a[i]);
	}
	for(int i=1;i<=kc+1;i++)
		while(q[i].w) cout<<q[i].find()<<' ',q[i].pop();
	return 0;
}

看不懂请不要乱叫。