#pragma once

#include <utility>

namespace cartesian {
using Key = int;
using Priority = int;

struct Tree;

struct Node;

struct Tree {
    Node* root = nullptr;

    bool empty() const {
        return root == nullptr;
    }

    void insert(Key x, Priority y);

    bool remove(Key x);

    bool find(Key x);

    std::pair<Tree, Tree> split(Key x, bool upper = false);

    static Tree merge(Tree l, Tree r);
};

struct Node {
    Key x;
    Priority y;
    Tree l, r;
};

// t -> l(<x) + r(>=x)
std::pair<Tree, Tree> Tree::split(Key x, bool upper) {
    if (empty())
        return {{},{}};
    bool root_will_be_right;
    if (upper)
        root_will_be_right = (root->x > x);
    else
        root_will_be_right = (root->x >= x);
    if (root_will_be_right) {
        auto [l, r] = root->l.split(x, upper);
        root->l = r;
        return {l, *this};
    } else {
        auto [l, r] = root->r.split(x, upper);
        root->r = l;
        return {*this, r};
    }
}

Tree Tree::merge(Tree l, Tree r) {
    if (l.empty())
        return r;
    if (r.empty())
        return l;
    if (r.root->y > l.root->y) {
        r.root->l = merge(l, r.root->l);
        return r;
    } else {
        l.root->r = merge(l.root->r, r);
        return l;
    }
}

bool Tree::find(Key x) {
    auto [l, r] = split(x);
    auto [rl, rr] = r.split(x, true);
    bool ans = rl.empty();
    r = merge(rl, rr);
    *this = merge(l, r);
    return ans;
}

bool Tree::remove(Key x) {
    auto [l, r] = split(x);
    auto [rl, rr] = r.split(x, true);
    bool ans = rl.empty();
    if (!rl.empty())
        delete rl.root;
    *this = merge(l, rr);
    return ans;
}

void Tree::insert(Key x, Priority y) {
    remove(x);
    auto [l, r] = split(x);
    Tree c{.root = new Node{
            .x = x,
            .y = y,
            .l = {},
            .r = {},
    }};
    *this = merge(merge(l, c), r);
}
}