#include <iostream>
#include <SFML/Graphics.hpp>
#include <SFML/Window.hpp>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>

struct Node {
    Node* left = nullptr;
    Node* right = nullptr;
    Node* prev = nullptr;
    int key = 0;
    int priority = 0;
    int color = 0;
    int height = 1;
    int size = 1;
};

void Swap(Node*& a, Node*& b) {

}

int Size(Node* treap) {
    return treap == nullptr ? 0 : treap->size;
}

int Recalc(Node* treap) {
    return Size(treap->left) + Size(treap->right) + 1;
}

Node* Create(int key, int color = 0) {
    Node* p = new Node;
    p->key = key;
    p->color = color;
    p->priority = std::rand() % 1000000000;
    return p;
}

bool CheckColor(Node* p) {
    if (p == nullptr) return true;
    if (p->color == 0) return true;
    if (p->color == 1) return false;
}

struct Avl {
    Node* root = nullptr;

    Node* find(int key, Node* search) {
        if (search == nullptr) {
            return nullptr;
        }
        if (search->key == key) {
            return search;
        }
        if (key > search->key) {
            return find(key, search->right);
        }
        if (key < search->key) {
            return find(key, search->left);
        }
    }

    void fixHeight(Node* p) {
        if (p == nullptr) {
            return;
        }
        int left = 0, right = 0;
        if (p->left != nullptr) {
            left = p->left->height;
            p->left->prev = p;
        }
        if (p->right != nullptr) {
            right = p->right->height;
            p->right->prev = p;
        }
        p->height = std::max(left, right) + 1;
    }

    int dif(Node* p) {
        if (p == nullptr) {
            return 0;
        }
        int left = 0, right = 0;
        if (p->left != nullptr) {
            left = p->left->height;
        }
        if (p->right != nullptr) {
            right = p->right->height;
        }
        return right - left;
    }

    void rotateSmall(Node*& p, bool direction) {
        if (p == nullptr) {
            return;
        }
        Node* q;
        if (!direction) {
            q = p->right;
            p->right = q->left;
            q->left = p;
        }
        else {
            q = p->left;
            p->left = q->right;
            q->right = p;
        }
        fixHeight(q);
        fixHeight(p);
        p = q;
    }

    void rotateBig(Node* p, bool direction) {
        if (p == nullptr) {
            return;
        }
        Node* q, * r;
        if (!direction) {
            q = p->right;
            r = q->left;
            r->left = p;
            r->right = q;
        }
        else {
            q = p->left;
            r = q->right;
            r->right = p;
            r->left = q;
        }
        fixHeight(p);
        fixHeight(q);
        fixHeight(r);
        p = r;
    }

    void balance(Node*& p) {
        if (p == nullptr) {
            return;
        }
        fixHeight(p);
        if (dif(p) == 2) {
            if (dif(p->right) < 0) {
                if (p->left != nullptr) {
                    rotateSmall(p, true);
                }
            }
            if (p->right != nullptr) {
                rotateSmall(p, false);
            }
        }
        if (dif(p) == -2) {
            if (dif(p->left) > 0) {
                if (p->right != nullptr) {
                    rotateSmall(p, false);
                }
            }
            if (p->left != nullptr) {
                rotateSmall(p, true);
            }
        }
        return;
    }

    bool insert(int key, Node*& p) {
        if (find(key, root) != nullptr) {
            return false;
        }
        if (p == nullptr) {
            p = Create(key);
            if (root == nullptr) {
                root = p;
            }
            return true;
        }
        if (key < p->key) {
            insert(key, p->left);
        }
        else {
            insert(key, p->right);
        }
        balance(p);
        return true;
    }

    Node* findMin(Node* search) {
        if (search == nullptr) {
            return nullptr;
        }
        if (search->left == nullptr) {
            return search;
        }
        return findMin(search->left);
    }

    void removeMin(Node*& search) {
        if (search == nullptr) {
            return;
        }
        if (search->left == nullptr) {
            Node* toDelete = search;
            search = search->right;
            delete toDelete;
            return;
        }
        removeMin(search->left);
        balance(search);
    }

    bool remove(int key, Node*& p) {
        if (p == nullptr) {
            return false;
        }
        if (key < p->key) {
            remove(key, p->left);
        }
        else if (key > p->key) {
            remove(key, p->right);
        }
        else {
            Node* left = p->left;
            Node* right = p->right;
            Node* toDelete = p;
            if (right == nullptr) {
                p = right;
            }
            p = findMin(right);
            removeMin(right);
            p->right = right;
            p->left = left;
            balance(p);
            delete toDelete;
            return true;
        }
        balance(p);
        return true;
    }
};

struct Treap {
    Node* root = nullptr;
    Node* cur = nullptr;
    Node* splitLeft = nullptr, * splitRight = nullptr;

    Node* find(int ind) {
        Node* treap = this->root;
        while (treap != nullptr) {
            int leftSize = Size(treap);
            if (leftSize == ind) {
                return treap;
            }
            if (leftSize < ind) {
                treap = treap->left;
            } else {
                treap = treap->right;
                ind -= leftSize + 1;
            }
        }
        return nullptr;
    }

    void split(int key, Node*& treap, Node*& left, Node*& right) {
        Node* newNode = nullptr;
        if (treap->key < key) {
            if (treap->right == nullptr) {
                right = nullptr;
                left = treap;
            } else {
                split(key, treap->right, newNode, right);
                left = treap;
                left->right = newNode;
            }
        } else {
            if (treap->left == nullptr) {
                left = nullptr;
                right = treap;
            } else {
                split(key, treap->left, left, newNode);
                right = treap;
                right->left = newNode;
            }
        }
    }

    Node* merge(Node* left, Node* right) {
        if (left == nullptr) {
            return right;
        }
        if (right == nullptr) {
            return left;
        }
        if (right->priority > left->priority) {
            Node* newNode = merge(left->right, right);
            left->right = newNode;
            return left;
        } else {
            Node* newNode = merge(left, right->left);
            right->left = newNode;
            return right;
        }
    }

    Node* insert(int key) {
        if (find(key) != nullptr) {
            return nullptr;
        }
        Node* node = Create(key);
        if (root == nullptr) {
            root = node;
            return root;
        }
        Node* left, * right;
        split(key, root, left, right);
        left = merge(left, node);
        root = merge(left, right);
        return root;
    }

    Node* remove(int key) {
        if (find(key) == nullptr) {
            return nullptr;
        }
        Node* left1, * left2, * right, * toDelete;
        split(key - 1, root, left1, right);
        split(key, left1, left2, toDelete);
        delete toDelete;
        root = merge(left2, right);
        return root;
    }

};

struct Splay {
    Node* root = nullptr;

    Node* find(int key, Node* search) {
        if (search == nullptr) {
            return nullptr;
        }
        if (search->key == key) {
            return splay(search);
        }
        if (key > search->key && search->right != nullptr) {
            return find(key, search->right);
        }
        if (key < search->key && search->left != nullptr) {
            return find(key, search->left);
        }
        return splay(search);
    }

    void rotate(Node* par, Node* chld) {
        Node* gpa = par->prev;
        if (gpa != nullptr) {
            if (gpa->left == par) {
                gpa->left = chld;
            }
            else {
                gpa->right = chld;
            }
        }
        if (par->left == chld) {
            par->left = chld->right;
            if (chld->right != nullptr) {
                chld->right->prev = par;
            }
            chld->right = par;
            par->prev = chld;
        }
        else {
            par->right = chld->left;
            if (chld->left != nullptr) {
                chld->left->prev = par;
            }
            chld->left = par;
            par->prev = chld;
        }
        chld->prev = gpa;
    }

    Node* splay(Node* p) {
        if (p->prev == nullptr) {
            return p;
        }
        Node* par = p->prev;
        Node* gpa = p->prev->prev;
        if (gpa == nullptr) {
            rotate(par, p);
            return p;
        }
        else {
            if (gpa->left == par && par->left == p) {
                rotate(gpa, par);
                rotate(par, p);
            }
            else {
                rotate(par, p);
                rotate(gpa, p);
            }
            return splay(p);
        }
    }

    void split(Node*& p, Node*& left, Node*& right, int key) {
        if (p == nullptr) {
            left = nullptr;
            right = nullptr;
            return;
        }
        p = find(key, p);
        if (p->key == key) {
            if (p->left != nullptr) {
                p->left->prev = nullptr;
            }
            if (p->right != nullptr) {
                p->right->prev = nullptr;
            }
            right = p->right;
            left = p->left;
            return;
        }
        if (p->key < key) {
            right = p->right;
            p->right = nullptr;
            if (right != nullptr) {
                right->prev = nullptr;
            }
            left = p;
            p = nullptr;
            return;
        }
        if (p->key > key) {
            left = p->left;
            p->left = nullptr;
            if (left != nullptr) {
                left->prev = nullptr;
            }
            right = p;
            p = nullptr;
            return;
        }

    }

    void insert(int key) {
        Node* left, * right;
        split(root, left, right, key);
        if (root == nullptr) {
            root = Create(key);
        }
        root->left = left;
        root->right = right;
        if (left != nullptr) {
            left->prev = root;
        }
        if (right != nullptr) {
            right->prev = root;
        }
    }

    Node* merge(Node* left, Node* right) {
        if (left == nullptr) return right;
        if (right == nullptr) return left;
        right = find(left->key, right);
        right->left = left;
        left->prev = right;
        return right;
    }

    bool remove(int key) {
        root = find(key, root);
        if (root->key != key) {
            return false;
        }
        Node* left = root->left, * right = root->right;
        if (left != nullptr) {
            left->prev = nullptr;
        }
        if (right != nullptr) {
            right->prev = nullptr;
        }
        root = merge(left, right);
        return true;
    }
};

struct RedBlack {


    Node* root = nullptr;

    void insert(int key) {
        Node* p = Create(key, 1);
        if (root == nullptr) {
            root = p;
            p->color = 0;
            return;
        }
        if (find(key, root) != nullptr) {
            return;
        }
        place(p, root);
        balance(p);
    }

    Node* find(int key, Node* search) {
        if (search == nullptr) {
            return nullptr;
        }
        if (search->key == key) {
            return search;
        }
        if (key > search->key) {
            return find(key, search->right);
        }
        if (key < search->key) {
            return find(key, search->left);
        }
    }

    void place(Node* q, Node* parent) {
        if (q->key > parent->key) {
            if (parent->right == nullptr) {
                parent->right = q;
                q->prev = parent;
                return;
            }
            place(q, parent->right);
        }
        else {
            if (parent->left == nullptr) {
                parent->left = q;
                q->prev = parent;
                return;
            }
            place(q, parent->left);
        }
    }

    void balance(Node*& p) {
        if (p->prev == nullptr) return;
        if (p->prev->color == 0) return;
        Node* par = p->prev, * gpa = p->prev->prev;
        Node* bro = (par == gpa->left ? gpa->right : gpa->left);
        if (bro != nullptr && bro->color == 1) {
            par->color = 0;
            bro->color = 0;
            balance(gpa);
        }
        if (CheckColor(bro)) {
            if (p == par->right && par == gpa->left) {
                p->prev = gpa;
                par->prev = p;
                par->right = p->left;
                p->left = par;
                gpa->left = p;
                std::swap(par, p);
            }
            else if (p == par->left && par == gpa->right) {
                p->prev = gpa;
                par->prev = p;
                par->left = p->right;
                p->right = par;
                gpa->right = p;
                std::swap(par, p);
            }
            if (gpa->left == par) {
                if (gpa->prev == nullptr) {
                    root = par;
                }
                else {
                    if (gpa->prev->left == gpa) {
                        gpa->prev->left = par;
                    }
                    else {
                        gpa->prev->right = par;
                    }
                }
                par->prev = gpa->prev;
                gpa->prev = par;
                gpa->left = par->right;
                if (par->right != nullptr) {
                    par->right->prev = gpa;
                }
                par->right = gpa;
            }
            else {
                if (gpa->prev == nullptr) {
                    root = par;
                }
                else {
                    if (gpa->prev->left == gpa) {
                        gpa->prev->left = par;
                    }
                    else {
                        gpa->prev->right = par;
                    }
                }
                par->prev = gpa->prev;
                gpa->prev = par;
                gpa->right = par->left;
                if (par->left != nullptr) {
                    par->left->prev = gpa;
                }
                par->left = gpa;
            }
            par->color = 0;
            gpa->color = 1;
            return;
        }
    }

    bool erase(int key) {
        Node* q = find(key, root);
        if (q == nullptr) {
            return false;
        }
        Node* min = findMin(q->right);
        if (min == nullptr) min = q;
        q->key = min->key;
        if (!CheckColor(min)) {
            if (min->prev->left == min) {
                min->prev->left = nullptr;
            }
            else {
                min->prev->right = nullptr;
            }
            delete min;
            return true;
        }
        if (!CheckColor(min->right)) {
            if (min->right != nullptr) {
                min->right->prev = q->prev;
                if (min->prev->left == min) {
                    min->prev->left = min->right;
                }
                else {
                    min->prev->right = min->right;
                }
                min->left->color = 0;
                delete min;
                return true;
            }
        }

        Node* toDelete = min;
        if (min->prev == nullptr) {
            root = nullptr;
            delete min;
            return true;
        }
        if (min->prev->left == min) {
            min->prev->left = min->right;
        }
        else {
            min->prev->right = min->right;
        }
        min = min->right;
        delete toDelete;
        rbalance(min);
        return true;
    }

    void rbalance(Node* p) {
        Node* par = p->prev, * bro = (p == par->left ? par->right : par->left);
        Node* d1 = bro->right, * d2 = bro->left;
        if (CheckColor(par) && CheckColor(bro) && CheckColor(d1) && CheckColor(d2)) {
            bro->color = 1;
            rbalance(par);
            return;
        }
        if (!CheckColor(par) && CheckColor(bro) && CheckColor(d1) && CheckColor(d2)) {
            par->color = 0;
            bro->color = 1;
            return;
        }
        if (CheckColor(bro) && CheckColor(d1) && !CheckColor(d2)) {
            bro->prev = par->prev;
            if (par->prev != nullptr) {
                if (par->prev->right == par) {
                    par->prev->right = bro;
                }
                else {
                    par->prev->left = bro;
                }
            }
            d2->color = 0;
            par->right = d1;
            bro->left = par;
            par->prev = bro;
            return;
        }
        if (CheckColor(bro) && !CheckColor(d1) && CheckColor(d2)) {
            par->right = d1;
            d1->prev = par;
            bro->prev = d1;
            bro->left = d1->right;
            d1->right = bro;
            d1->color = 0;
            bro->color = 1;
            std::swap(d1, bro);
            std::swap(d1, d2);
            bro->prev = par->prev;
            if (par->prev != nullptr) {
                if (par->prev->right == par) {
                    par->prev->right = bro;
                }
                else {
                    par->prev->left = bro;
                }
            }
            d2->color = 0;
            par->right = bro->left;
            bro->left = par;
            par->prev = bro;
            return;
        }
        if (!CheckColor(bro)) {
            if (par->prev != nullptr) {
                if (par->prev->right == par) {
                    par->prev->right = bro;
                }
                else {
                    par->prev->left = bro;
                }
            }
            bro->prev = par->prev;
            par->prev = bro;
            par->right = d1;
            bro->left = par;
            par->color = 1;
            bro->color = 0;
            if (d2 != nullptr) {
                d2->color = 1;
            }
            balance(p);
            return;
        }
        return;
    }

    Node* findMin(Node* p) {
        if (p == nullptr) {
            return nullptr;
        }
        if (p->left == nullptr) {
            return p;
        }
        return findMin(p->left);
    }
};



void InOrder(Node* p, int layer = 0) {
    if (p == nullptr) return;
    InOrder(p->left, layer + 1);
    std::cout << p->key << " ";
    InOrder(p->right, layer + 1);
}

void TreeOrder(Node* p) {
    int layer = 0;
    std::queue<std::pair<Node*, int>> queue;
    std::pair<Node*, int> blank;
    if (p != nullptr) {
        blank = { p, layer };
        queue.push(blank);
    }
    while (!queue.empty()) {
        if (queue.front().second > layer) {
            std::cout << "\n";
            ++layer;
        }
        Node* q = queue.front().first;
        std::cout << q->key << " ";
        queue.pop();
        if (q->left != nullptr) {
            blank.second = layer + 1;
            blank.first = q->left;
            queue.push(blank);
        }
        if (q->right != nullptr) {
            blank.second = layer + 1;
            blank.first = q->right;
            queue.push(blank);
        }
    }
}


sf::Font* font;

sf::Color textColor = sf::Color(232, 197, 71), backgroundColor = sf::Color(72, 64, 65), elementColor = sf::Color(254, 233, 225), fillColor = sf::Color(67, 67, 113), reactColor = sf::Color(217, 3, 104);

struct RenderNode {
    sf::RectangleShape rect;
    sf::Text text;
    int height = 0;
    Node* node = nullptr;
    int key = 0;
    sf::Vector2f scale;
    RenderNode* left = nullptr, * right = nullptr;

    void create(Node* node, int key, int height, float scale) {
        this->node = node;
        this->key = key;
        this->text.setString(std::to_string(key));
        this->height = height;

        sf::Vector2f sc = { scale, scale };
        this->scale = sc;

        rect.setSize(sf::Vector2f(150, 60));

        //text.setOrigin(text.getGlobalBounds().width / 2, text.getGlobalBounds().height / 2);
        rect.setOrigin(75, 30);
        text.setOrigin(75, 20);

        text.setFont(*font);
        rect.setOutlineThickness(1);

        rect.setFillColor(fillColor);
        text.setFillColor(textColor);
        rect.setOutlineColor(elementColor);

        text.setScale(this->scale);
        rect.setScale(this->scale);
    }

    void grow(sf::Vector2f scale) {
        this->scale = scale;
        text.setScale(scale);
        rect.setScale(scale);
    }

    void setPos(sf::Vector2f pos) {
        rect.setPosition(pos);
        text.setPosition(pos);
    }

    void draw(sf::RenderWindow& window) {
        window.draw(rect);
        window.draw(text);
    }
};

struct RenderTree {
    std::vector<sf::Vertex> connections;
    RenderNode* root = nullptr;
    int height;

    void create(Node* tree, sf::Vector2f pos, float scale) {
        int height = 0;
        RenderNode* rend = createNodes(tree, height, scale);
        root = rend;
        positionNodes(rend, pos, height);
        this->height = height;
    }

    void positionNodes(RenderNode* rend, sf::Vector2f pos, int height) {
        if (rend == nullptr) return;
        rend->setPos(pos);
        positionNodes(rend->left, { pos.x - 80 * (int)pow(2, height - 2) * rend->scale.x, pos.y + 200 * rend->scale.x }, height - 1);
        positionNodes(rend->right, { pos.x + 80 * (int)pow(2, height - 2) * rend->scale.x , pos.y + 200 * rend->scale.x}, height - 1);
        return;
    }

    RenderNode* createNodes(Node* tree, int& height, float scale) {
        if (tree == nullptr) {
            return nullptr;
        }

        int h1 = height, h2 = height;
        RenderNode* rend = new RenderNode;
        rend->left = createNodes(tree->left, h1, scale);
        rend->right = createNodes(tree->right, h2, scale);
        height = std::max(h1, h2) + 1;
        rend->create(tree, tree->key, height, scale);
        return rend;
    }

    void scale(RenderNode* rend, float scaleNum) {
        if (rend == nullptr) return;
        sf::Vector2f s = { scaleNum, scaleNum };
        rend->grow(s);
        scale(rend->left, scaleNum);
        scale(rend->right, scaleNum);
    }

    void draw(sf::RenderWindow& window) {

        drawNodes(window, root);
    }

    void drawNodes(sf::RenderWindow& window, RenderNode* rend) {
        if (rend == nullptr) return;
        if (rend->left != nullptr) {
            sf::Vector2f pos1, pos2;
            pos1 = { rend->rect.getPosition().x, rend->rect.getPosition().y };
            pos2 = { rend->left->rect.getPosition().x, rend->left->rect.getPosition().y};
            sf::Vertex line[] = {
                sf::Vertex(pos1),
                sf::Vertex(pos2)
            };
            window.draw(line, 2, sf::Lines);
        }
        if (rend->right != nullptr) {
            sf::Vector2f pos1, pos2;
            pos1 = { rend->rect.getPosition().x, rend->rect.getPosition().y };
            pos2 = { rend->right->rect.getPosition().x, rend->right->rect.getPosition().y };
            sf::Vertex line[] = {
                sf::Vertex(pos1),
                sf::Vertex(pos2)
            };
            window.draw(line, 2, sf::Lines);
        }
        rend->draw(window);
        drawNodes(window, rend->left);
        drawNodes(window, rend->right);
    }

    void clear() {
        connections.clear();
        clearNodes(root);
        root = nullptr;
    }

    void clearNodes(RenderNode* rend) {
        if (rend == nullptr) {
            return;
        }
        clearNodes(rend->left);
        clearNodes(rend->right);
        delete rend;
    }

   /* bool contains(float x, float y, int type, RenderNode* node = nullptr, bool first = false) {
        if (node == nullptr && !first) {
            node = root;
            first = true;
        }
        if (node == nullptr) return;
        if (node->rect.getGlobalBounds().contains(x, y)) {
            erase()
        }
    }*/
};

void InOrder2(RenderNode* p, int layer = 0) {
    if (p == nullptr) return;
    InOrder2(p->left, layer + 1);
    std::cout << p->key << " ";
    InOrder2(p->right, layer + 1);
}

void MousePressed(float x, float y) {

}

int main() {
    sf::RenderWindow window(sf::VideoMode(1000, 1000), "FUNKY GROOVY COME TO THE CLUB FOR FREE AND GET YOURSELF A FREE DRINK");

    RedBlack splay;
    RenderTree renderTree;
    sf::Vertex line[] =
    {
        sf::Vertex(sf::Vector2f(10.f, 10.f)),
        sf::Vertex(sf::Vector2f(150.f, 150.f))
    };

    font = new sf::Font;
    if (!font->loadFromFile("UbuntuMono-Regular.ttf")) {
        std::cout << "err\n";
    }

    sf::Vector2f treePos = { 500, 50 };
    float scale = 1;

    while (window.isOpen()) {


         sf::Event event;
         while (window.pollEvent(event)) {
             if (event.type == sf::Event::Closed) {
                 window.close();
             }
             if (event.type == sf::Event::KeyPressed) {
                 if (event.key.code == sf::Keyboard::Enter) {
                     renderTree.clear();
                     int k = 0;
                     while (k != 556) {
                         std::cin >> k;
                         splay.insert(k);
                     }
                     InOrder(splay.root);
                     std::cout << '\n';

                     renderTree.create(splay.root, treePos, scale);

                     InOrder2(renderTree.root);
                 }
                 if (event.key.code == sf::Keyboard::P) {
                     if (scale <= 0.2) {
                         scale += 0.02;
                     }
                     else {
                        scale += 0.1;
                     }

                     renderTree.scale(renderTree.root, scale);
                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                 }
                 if (event.key.code == sf::Keyboard::O) {
                     if (scale <= 0.2 && scale > 0.02) {
                         scale -= 0.02;
                         renderTree.scale(renderTree.root, scale);
                         renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                     }
                     else if (scale > 0.2) {
                         scale -= 0.1;
                         renderTree.scale(renderTree.root, scale);
                         renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                     }

                 }
                 if (event.key.code == sf::Keyboard::Up) {
                     treePos.y += 5 * scale * 10;
                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                 }
                 if (event.key.code == sf::Keyboard::Down) {
                     treePos.y -= 5 * scale * 10;
                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                 }
                 if (event.key.code == sf::Keyboard::Left) {
                     treePos.x += 5 * scale * 10;
                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                 }
                 if (event.key.code == sf::Keyboard::Right) {
                     treePos.x -= 5 * scale * 10;
                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
                 }

             }
         }


         window.clear(backgroundColor);

         renderTree.draw(window);

         window.display();
    }
}

/*
Avl avl;
    while (true) {
        int a;
        std::cin >> a;
        if (a == 0) {
            InOrder(avl.root);
            std::cout << "\n";
            TreeOrder(avl.root);
        }
        if (a == 1) {
            int key;
            std::cin >> key;
            std::cout << avl.insert(key, avl.root) << "\n";
        }
        if (a == 2) {
            int key;
            std::cin >> key;
            std::cout << avl.remove(key, avl.root) << "\n";
        }
        if (a >= 3) {
            for (int i = 0; i < a; ++i) {
                int k;
                int key;
                std::cin >> key;
                std::cout << avl.insert(key, avl.root) << "\n";
            }
        }
    }
*/

/*
5
3 10 15 30 29


437
3485
238
483
285
22
355
348
345
23
25699
8346867
934988
483276
2931
59328528
283582385
38723
237582358
2
32735285
69
1585
3382
384
23415
2643
523
247724
999999999
556
*/