$rt$

#include<bits/stdc++.h>
using namespace std;
int a[100005];
void qs(int a[],int left,int right){
	if(left>=right)return;
	int i=left,j=right;
	int benc=rand()%(right-left)+left;
	swap(a[benc],a[left]);
	benc=a[left];
	while(i<j){
		while(a[j]>=benc&&i<j)j--;
		swap(a[i],a[j]);		
		while(a[i]<=benc&&i<j)i++;
		swap(a[i],a[j]);
	}
	if(left<i-1)qs(a,left,i-1);
	if(i+1<right)qs(a,i+1,right);
	return;
}
int main(){
	int n;scanf("%d",&n);
	for(register int i=1;i<=n;i++)
    		scanf("%d",a+i);
	qs(a,1,n);
	for(register int i=1;i<=n;i++)
    		printf("%d",a[i]);
	return 0;
}

$O2$能过，但不想用