Seminar9

#include <iostream>
#include <stack>
#include <vector>

// Возвращает индекс, где разместится опорный элемент. [l, r)
inline int Partition(std::vector<int>& v, int l, int r) {
  if (r - l <= 1) return 0;
  const int& pivot = v[r - 1];
  int i = l, j = r - 2;
  while (i <= j) {
    // Не проверяем, что i < n - 1, т.к. a[n - 1] == pivot.
    for (; v[i] < pivot; ++i ) {}
    for (; j >= l && !(v[j] < pivot); --j) {}
    if (i < j) std::swap(v[i++], v[j--]);
  }
  std::swap(v[i], v[r - 1]);
  return i;
}

/*void foo(int p1, int p2) {
  if (condition) return;
  ...AAA...
  foo(x1, x2);
}
// ...AAA...   ...AAA...  ...AAA...
void foo(int p1, int p2) {
  while (!condition) {
    ...AAA...
    p1 = x1, p2 = x2;
  }
}*/

/*void foo(int p1, int p2) {
  //...AA1...
  if (cond1) foo(x1, x2);
  if (cond2) foo(x3, x4);
  if (cond3) foo(x5, x6);
}

void foo2() {
  std::stack<std::pair<int, int>> params_stack;
  params_stack.push({0, 100});
  while (!params_stack.empty()) {
    auto param = params_stack.top(); params_stack.pop();
    //...AA1(param)...
    if (cond3) params_stack.push({5, 6});
    if (cond2) params_stack.push({3, 4});
    if (cond1) params_stack.push({1, 2});
  }
}*/

// Сортировка на диапазоне [l, r)
void QuickSort(std::vector<int>& v, int l, int r) {
  while (r - l > 1) {
    int pivot_pos = Partition(v, l, r);
    QuickSort(v, l, pivot_pos);
    //QuickSort(v, pivot_pos + 1, r);
    l = pivot_pos + 1;
  }
}

void QuickSort(std::vector<int>& v) {
  if (v.size() <= 1) return;
  QuickSort(v, 0, v.size());
}

int main() {
  int n = 0;
  std::cin >> n;
  std::vector<int> v(n);
  for (int& x : v) std::cin >> x;
  QuickSort(v);
  for (int x : v) std::cout << x << " ";
  return 0;
}