// Подробные комментарии добавлю позже.
#include <bits/stdc++.h>
using namespace std;

mt19937 rng;

struct node
{
    int x, y;

    int l, r;

// Относительно вероятные одиночные совпадения <<игреков>>, если в дереве много сотен тысяч вершин.
// Из-за этого могут возникнуть проблемы с однозначностью дерева. Может иметь смысл сделать <<игреки>>
// 64-битными числами и использовать mt19937_64 вместо mt19937.
    node (const int x_) : x(x_), y(rng()), l(-1), r(-1), cnt(1) {}
};

struct treap_manager
{
    vector<node> v;

    int create_vertex (const int x)
    {
        const int ans = int(v.size());
        v.emplace_back(x);
        return ans;
    }

    /// <x, >=x
    pair<int, int> split (const int t, const int x)
    {
        if (t == -1)
            return {-1, -1};

        if (v[t].x < x)
        {
            auto [l, r] = split(v[t].r, x);
            v[t].r = l;
            return {t, r};
        }
        else
        {
            auto [l, r] = split(v[t].l, x);
            v[t].l = r;
            return {l, t};
        }
    }

    int merge (const int l, const int r)
    {
        if (l == -1)
            return r;
        if (r == -1)
            return l;

        if (v[l].y < v[r].y)
        {
            v[r].l = merge(l, v[r].l);
            return r;
        }
        else
        {
            v[l].r = merge(v[l].r, r);
            return l;
        }
    }

    int del (const int root, const int x)
    {
        auto [l, tmp] = split(root, x);
        auto [m, r] = split(tmp, x + 1);
        /// m -> дерево из x
        return merge(l, r);
    }

    int ins (const int root, const int x)
    {
        auto [l, r] = split(root, x);
        const int m = create_vertex(x);
        return merge(merge(l, m), r);
    }

    bool find (const int root, const int x)
    {
        if (root == -1)
            return false;

        if (v[root].x == x)
            return true;

        if (x < v[root].x)
            return find(v[root].l, x);
        return find(v[root].r, x);
    }
};

int main()
{
    treap_manager info;

    int root = -1;

    root = info.ins(root, 11);
    root = info.ins(root, 7);
    root = info.ins(root, 11);

    assert(info.find(root, 11));
    assert(info.find(root, 7));
    assert(!info.find(root, 4));

    root = info.del(root, 11);
    assert(!info.find(root, 11));
    assert(info.find(root, 7));
}