#include<bits/stdc++.h>
using namespace std;

int a[114514];

void Quicksort(int l,int r);

int main()
{
    freopen("working.in","r",stdin);
    freopen("working.out","w",stdout);
    int n;
    cin>>n;
    srand(time(0));
    for(int i=1;i<=n;i++)
    {
        a[i]=rand()%10000;
        printf("%4d ",a[i]);
    }
    Quicksort(1,n);
    for(int i=1;i<=n;i++)
    {
        printf("%4d ",a[i]);
    }
    return 0;
}

//Function Implementation

void Quicksort(int l,int r)
{
    if(l>=r) return ; 
    int i=l,j=r;
    int key=a[l];
    while(i<j)
    {
        while(i<j && a[j]>=key) j--;
        a[i]=a[j];
        while(i<j && a[i]<=key) i++;
        a[j]=a[i];
        a[i]=key;
    }
    Quicksort(l,i-1);
    Quicksort(i+1,r);
}