#include <bits/stdc++.h>

using namespace std;

struct lst {
    lst *next = nullptr, *prev = nullptr;
    int key;

    lst() {}
};

lst* get_end(lst *t) {
    if (t->next == nullptr) return t;
    lst *c = t;
    while (c->next->next != nullptr)
        c = c->next;
    return c;
}

pair<lst*, lst*> split(lst *t, int k) {
    if (k == 0)
        return {nullptr, t};
    int cnt = 0;
    lst *c = t;
    while (c->next != nullptr) {
        ++cnt;
        if (cnt == k) {
            lst *tm = c->next;
            c->next->prev = nullptr;
            c->next = new lst();
            c->next->prev = c;
            return {t, tm};
        }
        c = c->next;
    }
    return {t, nullptr};
}

lst* merge(lst *l, lst *r) {
    if (l == nullptr) return r;
    if (l->next == nullptr) {delete(l); return r;}
    lst *t = get_end(l);
    delete(t->next);
    t->next = r;
    r->prev = t;
    return l;
}

mt19937 gen(time(0));
uniform_int_distribution<int> dis(0, 1148822869);

void read(lst *t, int n) {
    lst *c = get_end(t);
    for (int i = 0; i < n; i++) {
        int x = dis(gen) % 1000000;
        //cin >> x;
        c->key = x;
        c->next = new lst();
        c->next->prev = c;
        c = c->next;
    }
}

void print(lst *t) {
    lst *c = t;
    int ls = -1000000;
    bool flg = 1;
    while (c->next != nullptr) {
        if (c->key < ls) {
        //    flg = 0;
        //    break;
        }
        ls = c->key;
        cout << c->key << ' ';
        c = c->next;
    }
    //out << (flg ? "YES" : "NO");
}

void print_back(lst *t) {
    lst *c = get_end(t);
    int ls = 1000000000;
    while (c != nullptr) {
        if (c->key > ls) {
            cout << "NO";
            return;
        }
        c = c->prev;
    }
    cout << "YES";
}

int get_size(lst *t) {
    int sz = 0;
    lst *c = t;
    while (c->next != nullptr) {
        c = c->next;
        ++sz;
    }
    return sz;
}

void append(lst *&t, int x) {
    t->key = x;
    t->next = new lst();
    t->next->prev = t;
    t = t->next;
}

void erase_list(lst *t) {
    while (t->next != nullptr) {
        lst *p = t->next;
        delete(t);
        t = p;
    }
    delete(t);
}

void merge_sort(lst *&t) {
    if (t->next == nullptr || t->next->next == nullptr) return;
    int sz = get_size(t);
    auto gg = split(t, sz / 2);
    lst *l = gg.first, *r = gg.second;
    merge_sort(l); merge_sort(r);
    lst *cl = l, *cr = r, *np;
    if (cl->key < cr->key) {
        np = cl;
        cl = cl->next;
    } else {
        np = cr;
        cr = cr->next;
    }
    lst *nl = np;
    while (cl->next != nullptr && cr->next != nullptr) {
        if (cl->key < cr->key) {
            nl->next = cl;
            cl->prev = nl;
            cl = cl->next;
            nl = cl;
        } else {
            nl->next = cr;
            cr->prev = nl;
            cr = cr->next;
            nl = cr;
        }
    }
    if (cl->next != nullptr) {
        nl->prev->next = cl;
        cl->prev = nl->prev;
    } else {
        nl->prev->next = cr;
        cr->prev = nl->prev;
    }
    t = np;
}

int main() {
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    lst *L = new lst();
    read(L, n);
    merge_sort(L);
    print(L);
    return 0;
}