#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
 
 
struct FastRandom {
    unsigned long long rnd;
 
    FastRandom(unsigned long long seed) {
        this->rnd = seed;
    }
 
    unsigned long long
    rand() {
        this->rnd ^= this->rnd << 21;
        this->rnd ^= this->rnd >> 35;
        this->rnd ^= this->rnd << 4;
        return this->rnd;
    }
};
 
 
template<typename T>
class SkipList {
    struct TreeNode {
        T key;
        unsigned level;
        unsigned id;
        bool headNode;
        bool deleted;
        unsigned skipDist;
        TreeNode *right;
        TreeNode *down;
 
        TreeNode(T key, unsigned level, unsigned id) :
                id(id),
                level(level),
                key(key),
                headNode(false),
                down(nullptr),
                right(nullptr),
                deleted(false),
                skipDist(0) {}
 
        void recursiveDelete() {
            if (right)
                right->recursiveDelete();
            if (this->headNode && down) {
                down->recursiveDelete();
                delete down;
            }
            delete right;
        }
    };
 
    unsigned maxLevels;
    unsigned ids;
    FastRandom randomizer;
 
    TreeNode *head;
 
    void dumpNodes(FILE *structure, TreeNode *node, unsigned group = 0) {
        if (node == nullptr)
            return;
        //        processDeletions(node);
        fprintf(structure, "node%u [label=\"%d\n(%u)\nskipped: %u\"", node->id, node->key, node->level, node->skipDist);
        if (node->deleted)
            fprintf(structure, ",style=filled, fillcolor=\"red\" ");
        if (node->headNode)
            fprintf(structure, ",style=filled, fillcolor=\"yellow\" ");
        fprintf(structure, "]\n");
        if (node->down != nullptr) {
            fprintf(structure, "node%u -> node%u [constraint=false, concentrate=true]\n", node->id, node->down->id);
            dumpNodes(structure, node->down);
        }
        if (node->right != nullptr) {
            fprintf(structure, "node%u -> node%u [concentrate=false]\n", node->id, node->right->id);
            dumpNodes(structure, node->right);
        }
 
    }
 
    bool inline spinACoin() {
        return this->randomizer.rand() <= ((unsigned long long) (-1)) / 2;
    }
 
    void processDeletions(TreeNode *node) {
        if (node == nullptr)
            return;
        if (node->right == nullptr)
            return;
        if (node->right->deleted == false)
            return;
        processDeletions(node->right);
        if (node->right->deleted) {
            if (node->right->right != nullptr) {
                node->right->right->skipDist += node->right->skipDist;
            }
            node->right = node->right->right;
        }
    }
 
    // key < node
    int compareWithNode(T key, TreeNode *node) {
        if (node == nullptr)
            return -1;
        if (key == node->key) return 0;
        return key < node->key ? -1 : 1;
    }
 
    bool insertRecursive(TreeNode *node, T key, TreeNode **insertedOne, unsigned *pos) {
        this->processDeletions(node);
        int compareRight = compareWithNode(key, node->right);
        unsigned posHere = *pos;
        if (compareRight == 0 || (node->key == key && node->headNode != true))
            return false;
        if (compareRight == 1) { // right elem is lower
            *pos += node->right->skipDist + 1;
            return insertRecursive(node->right, key, insertedOne, pos);
        } else {// (compareRight == -1) // want go down
            if (node->level == 1) {
                *(insertedOne) = new TreeNode(key, 1, ++(this->ids));
                (*(insertedOne))->right = node->right;
                node->right = *(insertedOne);
                return true;
            } else {
                bool possibleLevelInsert = insertRecursive(node->down, key, insertedOne, pos);
                if (!possibleLevelInsert) {
                    if (node->right != nullptr && *insertedOne != nullptr) {
                        node->right->skipDist++;
                    }
                    return false;
                }
                if (node->level == 1)
                    return true;
                bool insertNow = this->spinACoin();
                if (!insertNow) {
                    if (node->right != nullptr) {
                        node->right->skipDist++;
                    }
                    return false;
                }
                TreeNode *newNode = new TreeNode(key, node->level, ++(this->ids));
                newNode->down = *(insertedOne);
                newNode->right = node->right;
                newNode->skipDist = (*pos - posHere);
                if (node->right != nullptr) {
                    node->right->skipDist -= newNode->skipDist;
                }
                node->right = newNode;
                *(insertedOne) = newNode;
                return true;
            }
        }
    }
 
    bool removeRecursive(TreeNode *node, T key) {
        processDeletions(node);
        if (node == nullptr)
            return false;
        int compareRight = compareWithNode(key, node->right);
        if (compareRight == 0) {
            if (compareRight == 0)
                node = node->right;
            while (node != nullptr) {
                node->deleted = true;
                node = node->down;
            }
            return true;
        }
        if (compareRight == 1) { // right elem is lower
            return removeRecursive(node->right, key);
        } else {// (compareRight == -1) // want go down
            bool res = removeRecursive(node->down, key);
            if (res && node->right != nullptr) {
                if (node->right->key == key) {
                    if (node->right->right != nullptr)
                        node->right->right->skipDist += node->right->skipDist;
                    node->right = node->right->right;
                } else {
                    if (node->right->skipDist != 0)
                        node->right->skipDist--;
                }
            }
            return res;
        }
    }
 
    TreeNode *deepWalkForKth(TreeNode *node, int k) {
        processDeletions(node);
        if (node == nullptr)
            return nullptr;
        if (k == 0)
            return node;
        if (node->right != nullptr) {
            if (k - (int) node->right->skipDist > 0)
                return deepWalkForKth(node->right, k - node->right->skipDist - 1);
        }
        return deepWalkForKth(node->down, k);
    }
 
public:
    SkipList(unsigned maxLevels = 4) :
            maxLevels(maxLevels),
            ids(0),
            randomizer(rand()),
            head(nullptr) {
        this->head = new TreeNode(0, this->maxLevels, ++(this->ids));
        this->head->headNode = true;
        TreeNode *pos = this->head;
        for (unsigned i = 1; i < maxLevels; ++i) {
            TreeNode *newNode = new TreeNode(0, this->maxLevels - i, ++(this->ids));
            newNode->headNode = true;
            pos->down = newNode;
            pos = newNode;
        }
    }
 
    void insert(T key) {
        key *= -1;
        TreeNode *insertedNode = nullptr;
        unsigned skippedNow = 0;
        insertRecursive(this->head, key, &insertedNode, &skippedNow);
    }
 
    void remove(T key) {
        key *= -1;
        removeRecursive(this->head, key);
    }
 
 
    void dumpTree() {
        FILE *structure = fopen("struct.gv", "wb");
        fprintf(structure, "strict digraph structure { \nrankdir=\"LR\"\noverlap = scale;\n");
        this->dumpNodes(structure, this->head);
        fprintf(structure, "}\n");
        fclose(structure);
        system("/usr/local/bin/dot -Gstart=5 -Tsvg struct.gv -o graph.svg");
    }
 
    T kThMaximum(int k) {
        TreeNode *result = deepWalkForKth(this->head, k);
        return result->key * (-1);
    }
 
    ~SkipList() {
        if (head)
            head->recursiveDelete();
        delete head;
    }
};