#include <stdio.h>

#define NMAX 500000
#define nil -1

int theArray[NMAX];

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

int N;

FILE *inputFile = fopen("algsort.in", "r");

#define BUFFER_SIZE 8192

char buff[BUFFER_SIZE];
int buffIt;

inline int getNumber() {
  int ret = 0;
  
  while (buff[buffIt] < '0' || buff[buffIt] > '9')
    if (++buffIt == BUFFER_SIZE)
      fread(buff, BUFFER_SIZE, 1, inputFile),
      buffIt = 0;

  while (buff[buffIt] >= '0' && buff[buffIt] <= '9') {
    ret = ret * 10 + buff[buffIt] - '0';

    if (++buffIt == BUFFER_SIZE) {
      buffIt = 0;
      fread(buff, BUFFER_SIZE, 1, inputFile);
    }
  }
  theTree[N] = nil;

  return ret;
}

void readArray() {
  N = getNumber();
  for (int i = 0; i < N; ++i) {
    theArray[i] = getNumber();
    theTree[i] = nil;
  }
}

unsigned _randomNumber = 238746582;
unsigned _randomShit = 1234567891;

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

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

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;
}