#include <iostream>
#include <algorithm>

struct Node {
    int value, height_ = 1;
    Node *left_, *right_;

    explicit Node(int val) {
        value = val;
        left_ = nullptr;
        right_ = nullptr;
        height_ = 1;
    }

    int balanceFactor() const {
        int left_height = left_ ? left_->getHeight() : 0;
        int right_height = right_ ? right_->getHeight() : 0;
        return right_height - left_height;
    }

    int getHeight() {
        if (!left_) {
            if (!right_) {
                height_ = 1;
            } else {
                height_ = right_->getHeight() + 1;
            }
        } else {
            if (!right_) {
                height_ = left_->getHeight() + 1;
            } else {
                height_ = std::max(left_->getHeight(), right_->getHeight()) + 1;
            }
        }
        return height_;
    }

    ~Node() = default;
};

class AVLTree {
public:
    Node *root_;
    int size_;

    AVLTree() {
        root_ = nullptr;
        size_ = 0;
    }

    ~AVLTree() {
        deleteAvl(root_);
    }

    void deleteAvl(Node *p) {
        if (p) {
            deleteAvl(p->left_);
            deleteAvl(p->right_);
            delete p;
        }
    }

    int *traversal() {
        int x = 1;
        int *y = reinterpret_cast<int *>(x);
        return y;
    }

    int *lowerBound(int value) {
        int x = 1;
        int *y = reinterpret_cast<int *>(x);
        return y;
    }

    int getHeight() {
        return root_ ? root_->getHeight() : 0;
    }

    void insert(int value) {
        if (!find(value)) {
            insert(value, root_);
            ++size_;
        }
    }

    void insert(int value, Node *&node) {
        if (!node) {
            node = new Node(value);
        } else if (value < node->value) {
            insert(value, node->left_);
        } else if (value > node->value) {
            insert(value, node->right_);
        }
        node = balance(node);
    }

    int *find(int value) {
        return root_ ? find(value, root_) : nullptr;
    }

    int *find(int value, Node *node) {
        if (!node) {
            return nullptr;
        } else if (node->value > value) {
            return find(value, node->left_);
        } else if (node->value < value) {
            return find(value, node->right_);
        } else {
            return &node->value;
        }
    }

    void erase(int value) {
        if (find(value)) {
            root_ = erase(root_, value);
            --size_;
        }
    }

    Node *erase(Node *node, int value) {
        if (!node) {
            return nullptr;
        } else if (node->value > value) {
            node->left_ = erase(node->left_, value);
        } else if (node->value < value) {
            node->right_ = erase(node->right_, value);
        } else {
            Node *root_left = node->left_;
            Node *root_right = node->right_;
            delete node;
            if (!root_right) {
                return root_left;
            }
            Node *new_node = findMin(root_right);
            new_node->right_ = removeMin(root_right);
            new_node->left_ = root_left;
        }
        return balance(node);
    }

    static Node *rotateRight(Node *node) {
        auto new_node = node->left_;
        node->left_ = new_node->right_;
        new_node->right_ = node;
        node->getHeight();
        new_node->getHeight();
        return new_node;
    }

    static Node *rotateLeft(Node *node) {
        auto new_node = node->right_;
        node->right_ = new_node->left_;
        new_node->left_ = node;
        node->getHeight();
        new_node->getHeight();
        return new_node;
    }

    Node *balance(Node *node) {
        node->getHeight();
        if (node->balanceFactor() == 2) {
            if (node->right_->balanceFactor() == -1) {
                node->right_ = rotateRight(node->right_);
            }
            return rotateLeft(node);
        }
        if (node->balanceFactor() == -2) {
            if (node->right_->balanceFactor() == 1) {
                node->left_ = rotateLeft(node->left_);
            }
            return rotateRight(node);
        }
        return node;
    }

    Node *findMin(Node *node) {
        if (node) {
            return node->left_ ? findMin(node->left_) : node;
        }
        return nullptr;
    }

    Node *removeMin(Node *node) {
        if (!node) {
            return nullptr;
        }
        if (!node->left_) {
            return node->right_;
        }
        node->left_ = removeMin(node->left_);
        return balance(node);
    }

    bool empty() {
        return size_ == 0;
    }

    Node *getRoot() {
        return root_;
    }

    int getSize() const {
        return size_;
    }
};