#pragma once

#include <cstdlib>
#include <random>
#include <vector>

using std::pair;

struct FastRandom {
    size_t rnd;

    explicit FastRandom(size_t seed) {
        this->rnd = seed;
    }

    size_t rand() {
        this->rnd ^= this->rnd << 21;
        this->rnd ^= this->rnd >> 35;
        this->rnd ^= this->rnd << 4;
        return this->rnd;
    }
};

template<typename T>
class Treap {
private:
    struct Node {
        T key;
        size_t prior;
        size_t left = -1, right = -1;

        Node(T key, size_t prior) :
                key(std::move(key)),
                prior(prior) {
        }
    };

public:
    void insert(T key) {
        if (size == 0) {
            head_ = newNode(std::move(key), random.rand());
            size = 1;
        } else {
            head_ = insert_(head_, std::move(key));
        }
    }

    void remove(const T &key) {
        if (size != 0)
            head_ = remove_(head_, key);
    }

    const T *find(const T &key) const {
        auto node = find_(head_, key);
        if (node != -1) {
            return &nodes[node].key;
        }
        return nullptr;
    }

    void reserve(size_t n) {
        nodes.reserve(n);
    }

private:
    size_t newNode(T key, size_t prior) {
        if (nextFree == -1) {
            nodes.emplace_back(std::move(key), prior);
            return nodes.size() - 1;
        }

        auto toReturn = nextFree;
        nodes[toReturn].key = std::move(key);
        nodes[toReturn].right = -1;
        nodes[toReturn].left = -1;
        nodes[toReturn].prior = prior;
        nextFree = nodes[nextFree].right;
        return toReturn;
    }

    void deleteNode(size_t index) {
        assert(index < nodes.size() && "Index deleted wrong");
        nodes[index].right = -1;
        if (nextFree == -1) {
            nextFree = index;
            return;
        }
        nodes[index].right = nextFree;
        nextFree = index;
    }

    pair<size_t , size_t> split_(size_t pNo, const T &key, bool equalOnTheLeft = false) {
        if (pNo == -1) // reached leaf
            return {-1, -1};
        auto* p = &nodes[pNo];
        if (p->key < key ||
            (equalOnTheLeft && p->key == key)) { // splitting right
            auto q = split_(p->right, key, equalOnTheLeft);

            // q.first has nodes of the right
            // subtree that are less than key
            p->right = q.first;

            return {pNo, q.second};
        } else { // splitting left
            auto q = split_(p->left, key, equalOnTheLeft);

            // q.second has nodes of the left
            // subtree that are greater or equal
            // to the key
            p->left = q.second;

            return {q.first, pNo};
        }
    }

    size_t merge_(size_t lNo, size_t rNo) {
        if (lNo == -1) // left is empty
            return rNo;
        if (rNo == -1) // right is empty
            return lNo;
        auto* l = &nodes[lNo];
        auto* r = &nodes[rNo];
        if (l->prior > r->prior) { // l has the new head.
            l->right = merge_(l->right, rNo);
            return lNo;
        } else { // r has the new head.
            r->left = merge_(lNo, r->left);
            return rNo;
        }
    }

    size_t find_(size_t nodeNo, const T &key) const {
        if (nodeNo == -1)
            return -1;
        for(const auto* node = &nodes[nodeNo]; nodeNo != -1; node = &nodes[nodeNo]) {
            if (node->key == key)
                return nodeNo;
            if (key > node->key) {
                nodeNo = node->right;
            } else {
                nodeNo = node->left;
            }
        }
        return -1;
    }

    size_t insert_(size_t head, T key) {
        auto split = split_(head, key);
        if (find_(split.second, key) != -1) {
            // Key exists already
            // Merge back
            return merge_(split.first, split.second);
        }
        auto newNodeNo = newNode(std::move(key), random.rand());
        size++;
        return merge_(split.first, merge_(newNodeNo, split.second));
    }

    size_t remove_(size_t head, const T &key) {
    auto split = split_(head, key);
    if (split.second) {
        auto secondSplit = split_(split.second, key, /*equalOnTheLeft=*/true);

        // Key exists, so delete it and merge
        auto everythingElse = secondSplit.second;
        if (secondSplit.first == -1) {
            // There's no element equal to key. Merge back.
            return merge_(split.first, everythingElse);
        }

        // We got node with key value in
        // secondSplit.first
        deleteNode(secondSplit.first);

        size--;
        return merge_(split.first, everythingElse);
    }
    // Key is not presented. Merge back.
    return merge_(split.first, split.second);
}

    FastRandom random = FastRandom(rand());
    std::vector<Node> nodes;
    size_t nextFree = -1;
    size_t head_ = -1;
    size_t size = 0;
};