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

using uid = std::uniform_int_distribution<int>;

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

struct Tree;

struct Node;

struct Tree {
    Node *root = nullptr;

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

    size_t size() const;

    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;
    size_t s;

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

// 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;
        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 (r.root->y > l.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;
    }
}

bool Tree::find(Key x) {
    if (empty())
        return false;
    if (root->x == x)
        return true;
    if (root->x < x)
        return root->r.find(x);
    else
        return root->l.find(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 (ans)
        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 = {},
            .s = 1,
    }};
    *this = merge(merge(l, c), r);
}

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

namespace ordered_set {
std::mt19937 rng;
using Key = int;

struct Tree;

struct Node;

struct Tree {
    Node *root = nullptr;

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

    size_t size() const;

    void insert(Key x);

    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;
    Tree l, r;
    size_t s;

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

// 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;
        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() - 1)(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;
    }
}

bool Tree::find(Key x) {
    if (empty())
        return false;
    if (root->x == x)
        return true;
    if (root->x < x)
        return root->r.find(x);
    else
        return root->l.find(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 (ans)
        delete rl.root;
    *this = merge(l, rr);
    return ans;
}

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

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

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

struct Tree;

struct Node;

struct Tree {
    Node *root = nullptr;

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

    size_t size() const;

    void insert(size_t pos, Value v);

    Value remove(size_t pos);

    Value at(size_t pos);

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

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

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

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

// t -> l(<x) + r(>=x)
std::pair<Tree, Tree> Tree::split(size_t L) {
    if (L > size())
        throw std::runtime_error("Impossible split");
    if (L == 0)
        return {{}, *this};
    if (L == size())
        return {*this, {}};
    bool root_will_be_right = L <= root->l.size();
    if (root_will_be_right) {
        auto [l, r] = root->l.split(L);
        root->l = r;
        root->recalc();
        return {l, *this};
    } else {
        auto [l, r] = root->r.split(L - root->l.size() - 1);
        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() - 1)(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::at(size_t pos) {
    if (pos >= size())
        throw std::runtime_error("Incorrect at");
    if (pos == root->l.size())
        return root->v;
    if (pos < root->l.size())
        return root->l.at(pos);
    return root->r.at(pos - root->l.size() - 1);
}

Value Tree::remove(size_t pos) {
    auto [l, r] = split(pos);
    auto [rl, rr] = r.split(1);
    Value answer = rl.root->v;
    delete rl.root;
    *this = merge(l, rr);
    return answer;
}

void Tree::insert(size_t pos, Value v) {
    auto [l, r] = split(pos);
    Tree c{.root = new Node{
            .v = v,
            .l = {},
            .r = {},
            .s = 1,
    }};
    *this = merge(merge(l, c), r);
}

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