aaaa

#include<bits/stdc++.h>
using namespace std;
int a[100001],b[100001],n;
void Amalgamate_Array(int left,int mid,int mid1,int right)
{
	memset(b,0,sizeof(b));
	int x=left,y=mid1,k=0;
	while(x<=mid and y<=right)
	{
		if(a[x]<=a[y]) b[++k]=a[x++];
		else b[++k]=a[y++];
	}
	while(x<=mid) b[++k]=a[x++];
	while(y<=right) b[++k]=a[y++];
	for(int i=1;i<=k;++i) a[left+i-1]=b[i];
	return;
}
void Merge_Sort(int l,int r)
{
	if(l<r)
	{
		int mid=(l+r)/2;
		Merge_Sort(l,mid);
		Merge_Sort(mid+1,r);
		Amalgamate_Array(l,mid,mid+1,r);
		for(int i=1;i<=n;++i) cout<<a[i]<<" ";
		cout<<endl;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	Merge_Sort(1,n);
}