#include <cstdio>

#define NMAX 500010
#define SMAX 16384

int A[NMAX];
int temp[NMAX];
int n;
int minRun;
int runs;

void Read();
void Print();

struct Run {
  int BaseAddr;
  int Size;
} S[SMAX];

int GetMinRun(int n) {
  int r = 0;
  while (n >= 64) {
    r |= n & 1;
    n >>= 1;
  }
  return n + r;
}

void swap(int& a, int& b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
}

void InsertSort(int *start, int* stop) {
  if (start == stop) {
    return;
  }
  int *p = start + 1;
  int *q;
  while (p != stop) {
    q = p - 1;
    while (q >= start && *q > *(q + 1)) {
      swap(*q, *(q + 1));
      q--;
    }
    p++;
  }
}

void Reverse(int* first, int* last) {
  while (first < last) {
    swap(*first, *last);
    first++;
    last--;
  }
}

void MergeRuns(bool above) {
  int *p, *q, *dest;
  int pLen, qLen;
  int i, j, k;
  if (above) {
    p = A + S[runs - 2].BaseAddr;
    pLen = S[runs - 2].Size;
    q = A + S[runs - 1].BaseAddr;
    qLen = S[runs - 1].Size;
    S[runs - 2].Size += S[runs - 1].Size;    
  } else {
    p = A + S[runs - 3].BaseAddr;
    pLen = S[runs - 3].Size;
    q = A + S[runs - 2].BaseAddr;
    qLen = S[runs - 2].Size;
    S[runs - 3].Size += S[runs - 2].Size;
    S[runs - 2] = S[runs - 1];
  } 
  runs--;
  if (pLen <= qLen) {
    dest = p;
    for (i = 0; i < pLen; ++i) {
      temp[i] = p[i];
    }
    k = i = j = 0;
    while (i < pLen && j < qLen) {
      if (temp[i] <= q[j]) {
        dest[k++] = temp[i++];
      } else {
        dest[k++] = q[j++];
      }
    }
    for (; i < pLen; ++i) {
      dest[k++] = temp[i];
    }
    for (; j < qLen; ++j) {
      dest[k++] = q[j];
    }
  }
  else {
    dest = q + qLen - 1;
    for (j = 0; j < qLen; ++j) {
      temp[j] = q[j];
    }
    i = pLen - 1;
    j = qLen - 1;
    while (i >= 0 && j >= 0) {
      if (p[i] <= temp[j]) {
        *dest = p[i];
        --i;
        --dest;
      } else {
        *dest = temp[j];
        --j;
        --dest;
      }
    }
    for (; i >= 0; --i) {
      *dest = p[i];
      --dest;
    }
    for (; j >= 0; --j) {
      *dest = temp[j];
      --dest;
    }
  }  
}

void TimSort() {
  if (n < 64) {
    InsertSort(A, A + n);
    return;
  }
  bool  inRun = false;
  bool  decreasing = A[1] < A[0];
  int   i;  
  int   runStart = 0;
  int   curLen = 2;
  minRun = GetMinRun(n);
  for (i = 2; i < n; ++i) {            
    if ((decreasing && A[i] >= A[i - 1]) || (!decreasing && A[i] < A[i - 1])) {
      if (decreasing) {
        Reverse(A + runStart, A + runStart + curLen - 1);
      }
      if (curLen < minRun) {
        curLen = minRun;
        InsertSort(A + runStart, A + runStart + curLen);
        S[runs].BaseAddr = runStart;
        S[runs].Size = curLen;
        ++runs;
      } else {
        S[runs].BaseAddr = runStart;
        S[runs].Size = curLen;
        runs++;
      }
      if (runs > 2 && (S[runs - 1].Size <= S[runs - 2].Size + S[runs - 3].Size || S[runs - 2].Size <= S[runs - 3].Size)) {
        if (S[runs - 1].Size < S[runs - 3].Size) {
          MergeRuns(true);
        } else {
          MergeRuns(false);
        }
      }
      runStart += curLen;
      i = runStart;
      curLen = 1;
      if (i + 1 < n) {
        if (A[i + 1] < A[i]) {
          decreasing = true;          
        } else {
          decreasing = false;
        }
        curLen = 2;
        i++;
      } else {
        break;
      }        
      continue;
    }    
    ++curLen;
  }
  S[runs].BaseAddr = runStart;
  S[runs].Size = n - runStart;
  runs++;
  if (decreasing) {
    Reverse(A + S[runs - 1].BaseAddr, A + S[runs - 1].BaseAddr + S[runs - 1].Size - 1);
  }
  while (runs > 1) {
    MergeRuns(true);
  }
}

int main() {
  freopen("algsort.in", "r", stdin);
  freopen("algsort.out", "w", stdout);

  Read();  
  TimSort();
  Print();  

  return 0;
}

void Read() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", A + i);
  }
}

void Print() {
  for (int i = 0; i < n; ++i) {
    printf("%d ", A[i]);
  }
}