#include <bits/stdc++.h>

using namespace std;

int rnd() {
    int x = rand() << 16;
    x ^= rand();
    return x;
}

struct Treap{
    int key, priority;
    Treap* left;
    Treap* right;
    int size;

    Treap() : key(0), priority(0), left(nullptr), right(nullptr), size(0) {}
    Treap(int x) : key(x), priority(rnd()), left(nullptr), right(nullptr), size(1) {}
};

int get_size(Treap* v) {
    return v ? v->size : 0;
}

void recalc(Treap* &v) {
    if (v)
        v->size = 1 + get_size(v->left) + get_size(v->right);
}

void merge(Treap* &v, Treap* l, Treap* r) {
    if (!l || !r) {
        v = l ? l : r;
    } else if (l->priority > r->priority) {
        merge(l->right, l->right, r);
        v = l;
    } else {
        merge(r->left, l, r->left);
        v = r;
    }
    recalc(v);
}

void split(Treap* v, Treap* &l, Treap* &r, int key) {
    if (!v) {
        l = r = nullptr;
    } else {
        int lsize = get_size(v->left);
        if (key <= lsize) {
            split(v->left, l, r, key);
            v->left = r;
            r = v;
        } else {
            split(v->right, l, r, key - lsize - 1);
            v->right = l;
            l = v;
        }
    }
    recalc(l); recalc(r);
}