int getRand() { return (rand()<<15) + rand(); }

struct Treap {
    Treap *l, *r;
    long long key, prior;
    long long size;

    Treap(int x) : key(x), prior(getRand()), l(nullptr), r(nullptr), size(1) {}
    void update() {
        size = 1 + (l? l->size : 0) + (r? r->size : 0);
    }
};

Treap* Merge(Treap* L, Treap* R) {
    if (L == nullptr) return R;
    if (R == nullptr) return L;
    if (L->prior > R->prior) {
        L->r = Merge(L->r, R);
        L->update();
        return L;
    }
    R->l = Merge(L, R->l);
    R->update();
    return R;
}

pair < Treap*, Treap* > Split(Treap* root, int splitkey) {
    if (root == nullptr) return {nullptr, nullptr};
    if (root->key <= splitkey) {
        auto res = Split(root->r, splitkey);
        root->r = res.first;
        root->update();
        return {root, res.second};
    }
    auto res = Split(root->l, splitkey);
    root->l = res.second;
    root->update();
    return {res.first, root};
}

Treap* Insert(Treap* root, int key) {
    auto res = Split(root, key);
    Treap* v = new Treap(key);
    return Merge(Merge(res.first, v), res.second);
}

Treap* Delete(Treap* root, int key) {
    /*
    auto res = Split(root, key - 1);
    auto res2 = Split(res.second, key);
    return Merge(res.fist, res2.second);
    */
    if (root == nullptr) return root;
    if (root->key == key) return Merge(root->l, root->r);
    if (root->key < key) {
        root->r = Delete(root->r, key);
        root->update();
    } else {
        root->l = Delete(root->l, key);
        root->update();
    }
    return root;
}

bool Search(Treap* root, int key) {
    if (root == nullptr) return false;
    if (root->key == key) return true;
    if (root->key < key) return Search(root->r, key);
    return Search(root->l, key);
}

int Kth(Treap* root, int k) {
    long long leftsize = root->l ? root->l->size : 0;
    if (leftsize == k - 1) return root->key;
    if (leftsize < k - 1) return Kth(root->r, k - leftsize - 1);
    return Kth(root->l, k);
}