#include <stdio.h>

#define NMAX 500000

int theArray[NMAX];

int theTree[NMAX];
int treeLinkLeft[NMAX];
int treeLinkRight[NMAX];
int treeNode;

int N;

void readArray() {
  FILE *f = fopen("algsort.in", "r");

  fscanf(f, "%d", &N);
  
  for (int i = 0; i < N; ++i) {
    fscanf(f, "%d", theArray + i);
  }

  fclose(f);
}

unsigned _randomNumber = 238746582;
unsigned _randomShit = 1234567891;

inline unsigned randomNumber() {
  return _randomNumber = (_randomNumber + _randomShit) % N;
}

void mixArray() {
  int tmp, j;
  for (int i = 0; i < N; ++i) {
    j = randomNumber();
    tmp = theArray[i];
    theArray[i] = theArray[j];
    theArray[j] = tmp;
  }
}

#define nil 0

inline bool isEmpty(int poz) {
  return theTree[poz] == nil;
}

void insertNumber(int aNumber) {
  int curPoz = 1;
  int lastPoz = 0;
  bool lastIsLeft = true;
  
  while (!isEmpty(curPoz)) {
    lastPoz = curPoz;
    
    if (theTree[curPoz] > aNumber) {
      curPoz = treeLinkLeft[curPoz];
      lastIsLeft = true;
    } else {
      curPoz = treeLinkRight[curPoz];
      lastIsLeft = false;
    }
  }
  
  ++treeNode;
  
  if (lastIsLeft) {
    treeLinkLeft[lastPoz] = treeNode;
  } else {
    treeLinkRight[lastPoz] = treeNode;
  }
  
  theTree[treeNode] = aNumber;
}

void createTree() {
  treeLinkLeft[0] = 1;
  
  for (int i = 0; i < N; ++i) {
    insertNumber(theArray[i]);
  }
}

int arrayIt;

void inorderTraversal(int treeIt) {
  if (!isEmpty(treeLinkLeft[treeIt]))
    inorderTraversal(treeLinkLeft[treeIt]);
  
  theArray[arrayIt++] = theTree[treeIt];

  if (!isEmpty(treeLinkRight[treeIt]))
    inorderTraversal(treeLinkRight[treeIt]);
}

void createSortedArray() {
  inorderTraversal(1);
}

void sortArray() {
  createTree();
  createSortedArray();
}

void writeArray() {
  FILE *f = fopen("algsort.out", "w");

  for (int i = 0; i < N; ++i) {
    fprintf(f, "%d ", theArray[i]);
  }

  fclose(f);
}

void solve() {
  readArray();
  mixArray();
  sortArray();
  writeArray();
}

int main() {
  solve();
  return 0;
}