pair<treap*, treap*> split(treap *&root, int key) {
    if(root == nullptr) {
        return {nullptr, nullptr};
    }
    int root_key = get_size(root->left);
    if(key > root_key) {
        pair<treap*, treap*> splitted = split(root->right, key);
        root->right = splitted.x;
        update(root);
        return {root, splitted.y};
    }
    else {
        pair<treap*, treap*> splitted = split(root->left, key);
        root->left = splitted.y;
        update(root);
        return {splitted.x, root};
    }
}