for_ildar

class Node
{
public:
    Node(int val, int prior) : val(val), prior(prior), size(1), l(nullptr), r(nullptr) {};
    Node* get_l() { relax(); return l; }
    Node* get_r() { relax(); return r; }
    void set_l(Node* l) {
        this->l = l;
        relax();
    }
    void set_r(Node* r) {
        this->r = r;
        relax();
    }
    int val;
    int size;
    int prior;
private:
    Node* l;
    Node* r;
    void relax();
};

void Node::relax() {
    int lSize = (l == nullptr ? 0 : l->size);
    int rSize = (r == nullptr ? 0 : r->size);
    size = lSize + rSize + 1;
}

Node* root = nullptr;

Node* merge(Node* t1, Node* t2) {
    if (t1 == nullptr)
        return t2;
    if (t2 == nullptr)
        return t1;
    if (t1->prior > t2->prior) {
        t1->set_r(merge(t1->get_r(), t2));
        return t1;
    }
    else {
        t2->set_l(merge(t1, t2->get_l()));
        return t2;
    }
}

pair<Node*, Node*> split(Node* t, int val) {
    if (t == nullptr)
        return make_pair(nullptr, nullptr);
    if (val > t->val) {
        auto newT = split(t->get_r(), val);
        t->set_r(newT.first);
        return make_pair(t, newT.second);
    }
    else {
        auto newT = split(t->get_l(), val);
        t->set_l(newT.second);
        return make_pair(newT.first, t);
    }
}

void emplace(int val, Node* t = root) {
    if (root == nullptr) {
        root = new Node(val, ((rand() << 16) | rand()));
        return;
    }
    auto p = split(t, val);
    root = merge(merge(p.first, new Node(val, (rand() << 16) | rand())), p.second);
}

void erase(int val, Node* t = root) {
    auto p1 = split(t, val);
    auto p2 = split(p1.second, val + 1);
    root = merge(p1.first, p2.second);
}

pair<int, int> get(int val, Node* t = root) {
    auto p = split(t, val);
    int res = p.second->size;
    root = merge(p.first, p.second);
    return make_pair(root->size - res, res);
}