#include <bits/stdc++.h>

using namespace std;

// корень
struct TNode {
    int x, y;
    TNode *left, *right;
};

// объединить два корня
TNode* merge(TNode* left, TNode* right) {
    if (!left)
        return right;
    if (!right)
        return left;
    if (left->y < right->y) {
        left->right = merge(left->right, right);
        return left;
    } else {
        right->left = merge(left, right->left);
        return right;
    }
}

// разделить два корня
pair<TNode*, TNode*> split(TNode* root, int x) {
    if (!root)
        return {nullptr, nullptr};
    if (root->x > x) {
        auto t=split(root->left, x);
        root->left = t.second;
        return {t.first, root};
    } else {
        auto t=split(root->right, x);
        root->right = t.first;
        return {root, t.second};
    }
}

// создать новый корень
TNode* new_node(int x) {
    return new TNode({x, rand(), nullptr, nullptr});
}

// вставить новый корень
TNode* insert(TNode* root, int x) {
    TNode* node = new_node(x);
    auto t=split(root, x);
    return merge(t.first, merge(node, t.second));
}

// удаляем корень
TNode* erase(TNode* root, int x) {
    auto t=split(root, x);
    auto tt=split(t.first, x-1);
    if (!tt.second)
        return merge(tt.first, t.second);
    else {
        TNode* node = merge(tt.second->left, tt.second->right);
        return merge(tt.first, merge(node, tt.second));
    }
}

// существует ли элемент
bool exists(TNode* root, int x) {
    if (!root)
        return false;
    if (root->x == x)
        return false;
    if (root->x > x)
        return exists(root->left, x);
    else
        return exists(root->right, x);
}

int main() {

}