govnosort

#include <bits/stdc++.h>

using namespace std;

template<typename T, typename Compare>
void my_sort(T t_begin, T t_end, Compare comp) {
    for (T it = t_begin + 1; it != t_end; ++it) {
        if (comp(*it, *(it - 1))) {
            T left = t_begin, right = it;
            if (comp(*left, *it)) {
                T mid = left + distance(left, right) / 2;
                while (mid != left) {
                    if (comp(*mid, *it)) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                    mid = left + distance(left, right) / 2;
                }
            } else
                right = left;
            for (T t = it; t != right; --t) {
                swap(*t, *(t - 1));
            }
        }
    }
}

template<typename T>
void my_sort(T t_begin, T t_end) {
    my_sort(t_begin, t_end, [](auto& it1, auto& it2){return it1 < it2;});
}

int main() {
    int a;
    cin >> a;
    vector<int> vc(a);
    for (auto& x : vc)
        cin >> x;
    my_sort(vc.begin(), vc.end());
    for (auto& x : vc)
        cout << x << ' ';

}