// Подробные комментарии добавлю позже.
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif // LOCAL
#include <bits/stdc++.h>
using namespace std;

mt19937 rng;
using ll = long long;

struct node
{
    int x, y;

    int l, r;

    int cnt;
    int mx;

// Относительно вероятные одиночные совпадения <<игреков>>, если в дереве много сотен тысяч вершин.
// Из-за этого могут возникнуть проблемы с однозначностью дерева. Может иметь смысл сделать <<игреки>>
// 64-битными числами и использовать mt19937_64 вместо mt19937.
    node (const int x_) : x(x_), y(rng()), l(-1), r(-1),
                          cnt(1), mx(x) {}
};

struct treap_manager
{
    vector<node> v;

    int create_vertex (const int x)
    {
        const int ans = int(v.size());
        v.emplace_back(x);
        return ans;
    }

    int cnt (const int t)
    {
        return t == -1 ? 0 : v[t].cnt;
    }

    /// all numbers >= 0
    int mx (const int t)
    {
        return t == -1 ? 0 : v[t].mx;
    }

    void update (const int t)
    {
        if (t != -1)
        {
            v[t].cnt = cnt(v[t].l) + 1 + cnt(v[t].r);
            v[t].mx = max({mx(v[t].l), v[t].x, mx(v[t].r)});
        }
    }


    /// k elements to the left, the rest to the right
    pair<int, int> split (const int t, const int k)
    {
        assert(0 <= k && k <= cnt(t));

        if (t == -1)
            return {-1, -1};

        if (cnt(v[t].l) < k)
        {
            auto [l, r] = split(v[t].r, k - cnt(v[t].l) - 1);
            v[t].r = l;
            update(t);
            return {t, r};
        }
        else
        {
            auto [l, r] = split(v[t].l, k);
            v[t].l = r;
            update(t);
            return {l, t};
        }
    }

    int merge (const int l, const int r)
    {
        if (l == -1)
            return r;
        if (r == -1)
            return l;

        if (v[l].y < v[r].y)
        {
            v[r].l = merge(l, v[r].l);
            update(r);
            return r;
        }
        else
        {
            v[l].r = merge(v[l].r, r);
            update(l);
            return l;
        }
    }

    int del (const int root, const int x)
    {
        auto [l, tmp] = split(root, x);
        auto [m, r] = split(tmp, x + 1);
        /// m -> дерево из x
        return merge(l, r);
    }

    int ins (const int root, const int x)
    {
        auto [l, r] = split(root, x);
        const int m = create_vertex(x);
        return merge(merge(l, m), r);
    }

    bool find (const int root, const int x)
    {
        if (root == -1)
            return false;

        if (v[root].x == x)
            return true;

        if (x < v[root].x)
            return find(v[root].l, x);
        return find(v[root].r, x);
    }

    int kth_smallest (const int root, const int k)
    {
        assert(root != -1);
        assert(0 <= k && k < v[root].cnt);

        const int l = v[root].l;
        if (k == cnt(l))
            return v[root].x;
        else if (k < cnt(l))
            return kth_smallest(v[root].l, k);
        else
            /// k >= v[l].cnt + 1;
            return kth_smallest(v[root].r, k - cnt(l) - 1);
    }

    void check_cnt (const int root)
    {
        if (root == -1)
            return;

        assert(cnt(root) == cnt(v[root].l) + 1 + cnt(v[root].r));
        check_cnt(v[root].l);
        check_cnt(v[root].r);
    }

    int find_smallest (int root)
    {
        while (v[root].l != -1)
            root = v[root].l;
        return v[root].x;
    }

    int kth_smallest_other (const int root, const int k)
    {
        assert(root != -1);
        assert(0 <= k && k < v[root].cnt);

        auto [l, r] = split(root, k);
        const int ans = find_smallest(root);
        merge(l, r);
        return ans;
    }

    int push_back (const int root, const int x)
    {
        const int ver = create_vertex(x);
        return merge(root, ver);
    }

    int push_front (const int root, const int x)
    {
        const int ver = create_vertex(x);
        return merge(ver, root);
    }

    int swap_segments (const int root, const int len,
                       int s1, int s2)
    {
        if (s1 > s2)
            swap(s1, s2);

        /// [s1, s1 + len), [s2, s2 + len)
        assert(0 <= s1 && s1 + len <= s2 && s2 + len <= cnt(root));

        array<int, 5> segs;
        tie(segs[0], segs[1]) = split(root, s1);
        tie(segs[1], segs[2]) = split(segs[1], len);
        tie(segs[2], segs[3]) = split(segs[2], s2 - len - s1);
        tie(segs[3], segs[4]) = split(segs[3], len);

        int new_root = -1;
        swap(segs[1], segs[3]);
        for (int i = 0; i < 5; i++)
            new_root = merge(new_root, segs[i]);
        return new_root;
    }

    void dfs_flatten (const int root, vector<int> &ans)
    {
        if (root == -1)
            return;

        dfs_flatten(v[root].l, ans);
        ans.push_back(v[root].x);
        dfs_flatten(v[root].r, ans);
    }

    vector<int> flatten (const int root)
    {
        vector<int> ans;
        dfs_flatten(root, ans);
        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    treap_manager info;
    int root = -1;

    const int n = 1000;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);

    for (int i = 0; i < n; i++)
        root = info.push_back(root, p[i]);

    mt19937 query_rng(132);

    uniform_int_distribution<int> len_distr(1, n / 2);
    while (true)
    {
        const int len = len_distr(query_rng);

        /// [len, n - len]
        uniform_int_distribution<int> s2_distr(len, n - len);
        const int s2 = s2_distr(query_rng);
        uniform_int_distribution<int> s1_distr(0, s2 - len);
        const int s1 = s1_distr(query_rng);

        swap_ranges(p.begin() + s1, p.begin() + s1 + len,
                    p.begin() + s2);

        root = info.swap_segments(root, len, s1, s2);

        assert(info.flatten(root) == p);
    }
}