pair<treap*, treap*> split(treap *a, int k) {
    if(a == nullptr) return {nullptr, nullptr};
//    cerr << (a->left == nullptr) << '\n';
    int l = ((a->left == nullptr) ? -1 : a->left->sz);
    if(k <= l) {
        pair<treap*, treap*> kek = split(a->left, k);
        a->left = kek.y;
        update(a);
        return {kek.x, a};
    }
    else {
        pair<treap*, treap*> kek = split(a->right, k - l - 1);
        a->right = kek.x;
        update(a);
        return {a, kek.y};
    }
}