#include <bits/stdc++.h>

using namespace std;

struct SegmTree {
    string name = "SegmTree";
    map<int, int> roots;

    struct Node {
        int l = 0, r = 0, sz = 0;
    };
    vector<Node> T = {{}};
    int n;

    int build(int b, int e, int pos) {
        int ret = T.size(); T.emplace_back();
        T[ret].sz = 1;

        if (b != e) {
            int m = (b + e) / 2;
            if (pos <= m) T[ret].l = build(b, m, pos);
            else T[ret].r = build(m + 1, e, pos);
        }
        return ret;
    }

    void update(int node) {
        T[node].sz = T[T[node].l].sz + T[T[node].r].sz;
    }


    pair<int, int> split(int node, int k) {
        int lsz = T[T[node].l].sz, l = node, r = T.size();
        T.emplace_back();

        if (k > lsz) tie(T[l].r, T[r].r) = split(T[l].r, k - lsz);
        else swap(T[l].r, T[r].r);
        if (k < lsz) tie(T[l].l, T[r].l) = split(T[l].l, k);
        update(l); update(r);
        return {l, r};
    }

    int merge(int a, int b) {
        if (!a or !b) return (a | b);

        T[a].l = merge(T[a].l, T[b].l);
        T[a].r = merge(T[a].r, T[b].r);
        update(a);
        return a;
    }

    SegmTree(vector<int>& V) : n(V.size()) {
        for (int i = 0; i < n; ++i)
            roots[i] = build(0, n - 1, V[i]);
        roots[n] = 0;
    }

    void split_for(int x) {
        auto it = prev(roots.upper_bound(x));
        if (it->first != x) {
            tie(it->second, roots[x]) = split(it->second, x - it->first);
        }
    }
    void Sort(int b, int e) {
        if (b == e) return;
        split_for(b); split_for(e);
        auto it = roots.find(b);

        int jn = 0;
        while (it->first != e) {
            jn = merge(jn, it->second);
            ++it; roots.erase(prev(it));
        }
        assert(T[jn].sz == (e - b));
        roots[b] = jn;
    }

    vector<int> ret;
    void dump(int node, int b, int e) {
        if (node == 0) return;
        if (b == e) { ret.push_back(b); return; }
        int m = (b + e) / 2;
        dump(T[node].l, b, m);
        dump(T[node].r, m + 1, e);
    }

    vector<int> Dump() {
        ret.clear();
        for (auto p : roots) {
            dump(p.second, 0, n - 1);
        }
        return ret;
    }
};

struct Treap {
    string name = "Treap";
    map<int, int> roots;
    int n;

    struct Node {
        int l = 0, r = 0, k = 0, p = 0, sz = 0;
    };
    vector<Node> T;

    void update(int node) {
        if (node == 0) return;
        T[node].sz = 1 + T[T[node].l].sz + T[T[node].r].sz;
    }


    pair<int, int> split(int node, int k) {
        if (k == 0) return {0, node};

        int lsz = T[T[node].l].sz, l, r;

        if (k > lsz)
            tie(T[node].r, r) = split(T[node].r, k - lsz - 1), l = node;
        else tie(l, T[node].l) = split(T[node].l, k), r = node;

        update(node);
        return {l, r};
    }

    pair<int, int> splitk(int node, int k) {
        if (node == 0) return {0, 0};

        int l, r;
        if (T[node].k < k)
            tie(T[node].r, r) = splitk(T[node].r, k), l = node;
        else tie(l, T[node].l) = splitk(T[node].l, k), r = node;

        update(node);
        return {l, r};
    }

    int merge(int a, int b) {
        if (!a or !b) return a + b;

        if (T[a].p < T[b].p) swap(a, b);
        int l, r;
        tie(l, r) = splitk(b, T[a].k);
        T[a].l = merge(T[a].l, l);
        T[a].r = merge(T[a].r, r);

        update(a);
        return a;
    }

    Treap(vector<int>& V) : n(V.size()), T(n + 1) {
        for (int i = 0; i < n; ++i) {
            T[i + 1].k = V[i];
            T[i + 1].p = rand() + 1;
            update(i + 1);
            roots[i] = i + 1;
        }
        roots[n] = 0;
    }

    void split_for(int x) {
        auto it = prev(roots.upper_bound(x));
        if (it->first != x) {
            tie(it->second, roots[x]) = split(it->second, x - it->first);
        }
    }
    void Sort(int b, int e) {
        if (b == e) return;
        split_for(b); split_for(e);
        auto it = roots.find(b);

        int jn = 0;
        while (it->first != e) {
            jn = merge(jn, it->second);
            ++it; roots.erase(prev(it));
        }
        assert(T[jn].sz == (e - b));
        roots[b] = jn;
    }

    vector<int> ret;
    void dump(int node) {
        if (node == 0) return;
        dump(T[node].l);
        ret.push_back(T[node].k);
        dump(T[node].r);
    }

    vector<int> Dump() {
        ret.clear();
        for (auto p : roots) {
            dump(p.second);
        }
        return ret;
    }
};

struct Brut {
    string name = "Brut";
    vector<int> V;
    Brut(vector<int> V) : V(V) {}
    void Sort(int b, int e) {
        sort(V.begin() + b, V.begin() + e);
    }
    vector<int> Dump() { return V; }
};

template<typename T>
ostream& operator<<(ostream& out, vector<T>& V) {
    for (auto x : V) out << x << " ";
    return out;
}

template<typename Solver> vector<int> Check(vector<int> V, vector<complex<int>> ops) {
    time_t tick = clock();
    Solver solver(V);
    for (auto op : ops) {
        solver.Sort(op.real(), op.imag());
    }
    auto got = solver.Dump();
    time_t tock = clock();
    cerr << solver.name << " time: " << 1.0 * (tock - tick) / CLOCKS_PER_SEC << endl;
    return got;
}

int main() {
    int its = 0;
    while (true) {

        int sz = 1 + rand() % 500000;
        vector<int> V(sz);
        for (int i = 0; i < sz; ++i)
            V[i] = i;
        random_shuffle(V.begin(), V.end());

        vector<complex<int>> ops;

        int opc = rand() % 80000 + 1;
        for (int i = 0; i < opc; ++i) {
            int b = rand() % sz;
            int e = rand() % (sz + 1);
            if (b > e) swap(b, e);
            ops.emplace_back(b, e);
        }

        auto resb = Check<Brut>(V, ops);
        auto rest = Check<Treap>(V, ops);
        auto ress = Check<SegmTree>(V, ops);

        if (resb != rest or resb != ress) {
            cerr << "Initial: " << V << endl;
            cerr << "Brut: " << resb << endl;
            cerr << "Treap: " << rest << endl;
            cerr << "SegmTree: " << ress << endl;
        }

        if ((++its) % 1 == 0) {
            cerr << "OK " << its << " iterations" << endl << endl;
        }
    }
    return 0;
}