#pragma once
#include <optional>
#include <random>
#include <algorithm>

using uid = std::uniform_int_distribution<int>;

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

struct Node;

struct Tree {
    Node* root = nullptr;

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

    size_t size() const;

    void insert(Key x, Value v, Priority y);

    std::optional<Value> find(Key x);

    std::optional<Value> remove(Key x);

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

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

struct Node {
    size_t s;
    Key x;
    Value v;
    Priority y;
    Tree l, r;

    void recalc() {
        s = 1 + l.size() + r.size();
    }
};

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

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

void insert(Key x, Value v, Priority y);

std::optional<Value> Tree::find(Key x) {
    if (empty())
        return {};
    if (root->x == x)
        return root->v;
    if (root->x > x)
        return root->l.find(x);
    return root->r.find(x);
}

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

void Tree::insert(Key x, Value v, Priority y) {
    remove(x);
    auto [l, r] = split(x);
    // новое дерево c
    Node *node_ptr = new Node{
            .s = 1,
            .x = x,
            .v = v,
            .y = y,
            .l = {},
            .r = {},
    };
    Tree c{.root = node_ptr};
    *this = merge(l, merge(c, r));
}

size_t Tree::size() const {
    if (empty()) return 0;
    return root->s;
}
}

namespace ordered_map {
std::mt19937 rng;
using Key = int;
using Value = int;

struct Node;

struct Tree {
    Node* root = nullptr;

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

    size_t size() const;

    void insert(Key x, Value v);

    std::optional<Value> find(Key x);

    std::optional<Value> remove(Key x);

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

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

struct Node {
    size_t s;
    Key x;
    Value v;
    Tree l, r;

    void recalc() {
        s = 1 + l.size() + r.size();
    }
};

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

Tree Tree::merge(Tree l, Tree r) {
    if (l.empty())
        return r;
    if (r.empty())
        return l;
    int decision_maker = uid(0, l.size() + r.size())(rng);
    if (decision_maker >= l.size()) {
        r.root->l = merge(l, r.root->l);
        r.root->recalc();
        return r;
    } else {
        l.root->r = merge(l.root->r, r);
        l.root->recalc();
        return l;
    }
}

std::optional<Value> Tree::find(Key x) {
    if (empty())
        return {};
    if (root->x == x)
        return root->v;
    if (root->x > x)
        return root->l.find(x);
    return root->r.find(x);
}

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

void Tree::insert(Key x, Value v) {
    remove(x);
    auto [l, r] = split(x);
    // новое дерево c
    Node *node_ptr = new Node{
            .s = 1,
            .x = x,
            .v = v,
            .l = {},
            .r = {},
    };
    Tree c{.root = node_ptr};
    *this = merge(l, merge(c, r));
}

size_t Tree::size() const {
    if (empty()) return 0;
    return root->s;
}
}

namespace smart_array {
std::mt19937 rng;
using Value = int;

struct Node;

struct Tree {
    Node* root = nullptr;

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

    size_t size() const;

    void insert(size_t p, Value v);

    Value find(size_t p);

    Value remove(size_t p);

    std::pair<Tree, Tree> split(size_t p);

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

struct Node {
    size_t s;
    Value v;
    Tree l, r;

    void recalc() {
        s = 1 + l.size() + r.size();
    }
};

std::pair<Tree, Tree> Tree::split(size_t p) {
    if (empty())
        return {{},{}};
    if (p == 0)
        return {{}, *this};
    if (p > size())
        throw std::runtime_error("Incorrect split");
    if (p == size())
        return {*this, {}};
    bool root_is_right = p <= root->l.size();
    if (root_is_right) {
        auto [l, r] = root->l.split(p);
        root->l = r;
        root->recalc();
        return {l, *this};
    } else {
        auto [l, r] = root->r.split(p - 1 - root->l.size());
        root->r = l;
        root->recalc();
        return {*this, r};
    }
}

Tree Tree::merge(Tree l, Tree r) {
    if (l.empty())
        return r;
    if (r.empty())
        return l;
    int decision_maker = uid(0, l.size() + r.size())(rng);
    if (decision_maker >= l.size()) {
        r.root->l = merge(l, r.root->l);
        r.root->recalc();
        return r;
    } else {
        l.root->r = merge(l.root->r, r);
        l.root->recalc();
        return l;
    }
}

Value Tree::find(size_t p) {
    if (p >= size())
        throw std::runtime_error("Incorrect find");
    if (p == root->l.size())
        return root->v;
    if (p < root->l.size())
        return root->l.find(p);
    return root->r.find(p - 1 - root->l.size());
}

Value Tree::remove(size_t p) {
    if (p >= size())
        throw std::runtime_error("Incorrect remove");
    auto [l, r] = split(p);
    auto [rl, rr] = r.split(1);
    Value ans = rl.root->v;
    delete rl.root;
    *this = merge(l, rr);
    return ans;
}

void Tree::insert(size_t p, Value v) {
    auto [l, r] = split(p);
    // новое дерево c
    Node *node_ptr = new Node{
            .s = 1,
            .v = v,
            .l = {},
            .r = {},
    };
    Tree c{.root = node_ptr};
    *this = merge(l, merge(c, r));
}

size_t Tree::size() const {
    if (empty()) return 0;
    return root->s;
}
}

namespace mass_operations {
std::mt19937 rng;
using Value = int;

struct Node;

struct Tree {
    Node* root = nullptr;

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

    size_t size() const;

    void insert(size_t p, Value v);

    Value find(size_t p);

    Value remove(size_t p);

    std::pair<Tree, Tree> split(size_t p);

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

struct Node {
    size_t s;
    Value v;
    Value promise;
    Tree l, r;

    void recalc() {
        s = 1 + l.size() + r.size();
    }
};

std::pair<Tree, Tree> Tree::split(size_t p) {
    if (empty())
        return {{},{}};
    if (p == 0)
        return {{}, *this};
    if (p > size())
        throw std::runtime_error("Incorrect split");
    if (p == size())
        return {*this, {}};
    bool root_is_right = p <= root->l.size();
    if (root_is_right) {
        root->l.root->v += root->promise;
        root->l.root->promise += root->promise;
        auto [l, r] = root->l.split(p);
        root->l = r;
        root->recalc();
        root->l.root->v -= root->promise;
        root->l.root->promise -= root->promise;
        return {l, *this};
    } else {
        root->r.root->v += root->promise;
        root->r.root->promise += root->promise;
        auto [l, r] = root->r.split(p - 1 - root->l.size());
        root->r = l;
        root->recalc();
        root->r.root->v -= root->promise;
        root->r.root->promise -= root->promise;
        return {*this, r};
    }
}

Tree Tree::merge(Tree l, Tree r) {
    if (l.empty())
        return r;
    if (r.empty())
        return l;
    int decision_maker = uid(0, l.size() + r.size())(rng);
    if (decision_maker >= l.size()) {
        r.root->l.root->v += r.root->promise;
        r.root->l.root->promise += r.root->promise;
        r.root->l = merge(l, r.root->l);
        r.root->recalc();
        r.root->l.root->v -= r.root->promise;
        r.root->l.root->promise -= r.root->promise;
        return r;
    } else {
        l.root->r.root->v += l.root->promise;
        l.root->r.root->promise += l.root->promise;
        l.root->r = merge(l.root->r, r);
        l.root->recalc();
        l.root->r.root->v -= l.root->promise;
        l.root->r.root->promise -= l.root->promise;
        return l;
    }
}

Value Tree::find(size_t p) {
    if (p >= size())
        throw std::runtime_error("Incorrect find");
    if (p == root->l.size())
        return root->v;
    if (p < root->l.size())
        return root->l.find(p) + root->promise;
    return root->r.find(p - 1 - root->l.size()) + root->promise;
}

Value Tree::remove(size_t p) {
    if (p >= size())
        throw std::runtime_error("Incorrect remove");
    auto [l, r] = split(p);
    auto [rl, rr] = r.split(1);
    Value ans = rl.root->v;
    delete rl.root;
    *this = merge(l, rr);
    return ans;
}

void Tree::insert(size_t p, Value v) {
    auto [l, r] = split(p);
    // новое дерево c
    Node *node_ptr = new Node{
            .s = 1,
            .v = v,
            .promise = 0,
            .l = {},
            .r = {},
    };
    Tree c{.root = node_ptr};
    *this = merge(l, merge(c, r));
}

size_t Tree::size() const {
    if (empty()) return 0;
    return root->s;
}
}
}