#include <iostream>

template <class ValueType>
class RBTree {
public:
    RBTree() {
        nil_ = new RBNode{ValueType(), true, nullptr, nullptr, nullptr};
        root_ = nil_;
        size_ = 0;
    }

    RBTree(const RBTree& other) {
        nil_ = new RBNode{ValueType(), true, nullptr, nullptr, nullptr};
        root_ = nil_;
        size_ = other.size_;
        if (other.root_ == other.nil_) {
            return;
        }
        root_ = new RBNode{other.root_->value, other.root_->isBlack, nil_, nil_, nullptr};
        deepCopy(other.root_, root_, other.nil_);
    }

    RBTree& operator=(const RBTree& other) {
        if (this == &other) {
            return *this;
        }
        if (root_ != nil_) {
            clear(root_);
        }

        if (root_ != nil_) {
            delete root_;
        }
        delete nil_;

        nil_ = new RBNode{ValueType(), true, nullptr, nullptr, nullptr};
        size_ = other.size_;

        if (other.root_ != other.nil_) {
            root_ = new RBNode{other.root_->value, other.root_->isBlack, nil_, nil_, nullptr};
            deepCopy(other.root_, root_, other.nil_);
        } else {
            root_ = nil_;
        }
        return *this;
    }

    ~RBTree() {
        clear(root_);
        if (root_ != nil_) {
            delete root_;
        }
        delete nil_;
    }

    size_t size() const {
        return size_;
    }

    bool empty() const {
        return root_ == nil_;
    }

    void insert(const ValueType& value) {
        RBNode* node = new RBNode{value, false, nil_, nil_, nullptr};
        if (root_ == nil_) {
            root_ = node;
            shuffleInsert(root_);
            size_++;
            return;
        }

        RBNode* current = root_;
        RBNode* tmp = nullptr;

        while (current != nil_) {
            tmp = current;
            if (current->value < node->value) {
                current = current->right;
            } else if (node->value < current->value) {
                current = current->left;
            } else {
                delete node;
                return;
            }
        }

        node->parent = tmp;
        if (tmp->value < node->value) {
            tmp->right = node;
        } else {
            tmp->left = node;
        }
        size_++;
        shuffleInsert(node);
    }

    void erase(const ValueType& value) {
        RBNode* node = root_;
        RBNode* current = nil_;
        RBNode* tmp_x;
        RBNode* tmp_y;
        while (node != nil_) {
            if (!(node->value < value || value < node->value)) {
                current = node;
            }

            if (node->value < value) {
                node = node->right;
            } else {
                node = node->left;
            }
        }

        if (current == nil_) {
            return;
        }

        tmp_y = current;
        bool y_original_color = tmp_y->isBlack;
        if (current->left == nil_) {
            tmp_x = current->right;
            rbTransplant(current, current->right);
        } else if (current->right == nil_) {
            tmp_x = current->left;
            rbTransplant(current, current->left);
        } else {
            tmp_y = minimum(current->right);
            y_original_color = tmp_y->isBlack;
            tmp_x = tmp_y->right;
            if (tmp_y->parent == current) {
                tmp_x->parent = tmp_y;
            } else {
                rbTransplant(tmp_y, tmp_y->right);
                tmp_y->right = current->right;
                tmp_y->right->parent = tmp_y;
            }

            rbTransplant(current, tmp_y);
            tmp_y->left = current->left;
            tmp_y->left->parent = tmp_y;
            tmp_y->isBlack = current->isBlack;
        }
        delete current;
        size_--;
        if (y_original_color) {
            shuffleDelete(tmp_x);
        }
    }

    ValueType* lower_bound(const ValueType& value) const {  // NOLINT
        RBNode* current = root_;
        ValueType* result = nullptr;

        while (current != nil_) {
            if (value < current->value) {
                result = &current->value;
                current = current->left;
            } else if (current->value < value) {
                current = current->right;
            } else {
                return &current->value;
            }
        }

        return result;
    }

    ValueType* find(const ValueType& value) const {
        RBNode* current = root_;
        // ValueType* result = nullptr;
        while (current != nil_) {
            if (current->value < value) {
                current = current->right;
            } else if (value < current->value) {
                current = current->left;
            } else {
                return &current->value;
            }
        }

        return nullptr;
    }

    ValueType* traversal() const {
        ValueType* nodes = new ValueType[size_];
        int index = 0;
        fill(nodes, root_, &index);

        return nodes;
    }

private:
    struct RBNode {
        ValueType value;
        bool isBlack;
        RBNode* left;
        RBNode* right;
        RBNode* parent;
    };

    RBNode* root_;
    RBNode* nil_;
    size_t size_;

    void shuffleInsert(RBNode* node) {
        if (node == root_) {
            root_->isBlack = true;
            return;
        }

        while (!node->parent->isBlack) {
            if (node->parent == node->parent->parent->left) {
                if (node->parent->parent->right && !node->parent->parent->right->isBlack) {
                    node->parent->isBlack = true;
                    node->parent->parent->right->isBlack = true;
                    node->parent->parent->isBlack = false;
                    node = node->parent->parent;
                } else {
                    if (node->parent->value < node->value) {
                        node = node->parent;
                        leftRotate(node);
                    }
                    node->parent->isBlack = true;
                    node->parent->parent->isBlack = false;
                    rightRotate(node->parent->parent);
                }
            } else {
                if (node->parent->parent->left && !node->parent->parent->left->isBlack) {
                    node->parent->isBlack = true;
                    node->parent->parent->left->isBlack = true;
                    node->parent->parent->isBlack = false;
                    node = node->parent->parent;
                } else {
                    if (node->value < node->parent->value) {
                        node = node->parent;
                        rightRotate(node);
                    }
                    node->parent->isBlack = true;
                    node->parent->parent->isBlack = false;
                    leftRotate(node->parent->parent);
                }
            }

            if (node == root_) {
                break;
            }
        }

        root_->isBlack = true;
    }

    void shuffleDelete(RBNode* node) {
        RBNode* uncle;
        while (node != root_ && node->isBlack) {
            if (node == node->parent->left) {
                uncle = node->parent->right;
                if (!uncle->isBlack) {
                    uncle->isBlack = true;
                    node->parent->isBlack = false;
                    leftRotate(node->parent);
                    uncle = node->parent->right;
                }

                if (uncle->left->isBlack && uncle->right->isBlack) {
                    uncle->isBlack = false;
                    node = node->parent;
                } else {
                    if (uncle->right->isBlack) {
                        uncle->left->isBlack = true;
                        uncle->isBlack = false;
                        rightRotate(uncle);
                        uncle = node->parent->right;
                    }

                    uncle->isBlack = node->parent->isBlack;
                    node->parent->isBlack = true;
                    uncle->right->isBlack = true;
                    leftRotate(node->parent);
                    node = root_;
                }
            } else {
                uncle = node->parent->left;
                if (!uncle->isBlack) {
                    uncle->isBlack = true;
                    node->parent->isBlack = false;
                    rightRotate(node->parent);
                    uncle = node->parent->left;
                }

                if (uncle->right->isBlack && uncle->left->isBlack) {
                    uncle->isBlack = false;
                    node = node->parent;
                } else {
                    if (uncle->left->isBlack) {
                        uncle->right->isBlack = true;
                        uncle->isBlack = false;
                        leftRotate(uncle);
                        uncle = node->parent->left;
                    }

                    uncle->isBlack = node->parent->isBlack;
                    node->parent->isBlack = true;
                    uncle->left->isBlack = true;
                    rightRotate(node->parent);
                    node = root_;
                }
            }
        }
        node->isBlack = true;
    }

    void leftRotate(RBNode* node) {
        RBNode* node_right = node->right;
        node->right = node_right->left;

        if (node->right != nil_) {
            node->right->parent = node;
        }

        node_right->parent = node->parent;
        if (!node->parent) {
            root_ = node_right;
        } else if (node == node->parent->left) {
            node->parent->left = node_right;
        } else {
            node->parent->right = node_right;
        }

        node_right->left = node;
        node->parent = node_right;
    }

    void rightRotate(RBNode* node) {
        RBNode* node_left = node->left;
        node->left = node_left->right;

        if (node->left != nil_) {
            node->left->parent = node;
        }

        node_left->parent = node->parent;
        if (!node->parent) {
            root_ = node_left;
        } else if (node == node->parent->left) {
            node->parent->left = node_left;
        } else {
            node->parent->right = node_left;
        }

        node_left->right = node;
        node->parent = node_left;
    }

    void clear(RBNode* node) {
        if (node == nil_) {
            return;
        }

        clear(node->left);
        clear(node->right);

        if (node->left != nil_) {
            delete node->left;
        }
        if (node->right != nil_) {
            delete node->right;
        }
    }

    void dfs(RBNode* node) {
        if (node == nil_) {
            return;
        }
        dfs(node->left);
        std::cout << node->value << std::endl;
        dfs(node->right);
    }

    RBNode* minimum(RBNode* node) {
        while (node->left != nil_) {
            node = node->left;
        }
        return node;
    }

    void rbTransplant(RBNode* node_u, RBNode* node_v) {
        if (node_u->parent == nullptr) {
            root_ = node_v;
        } else if (node_u == node_u->parent->left) {
            node_u->parent->left = node_v;
        } else {
            node_u->parent->right = node_v;
        }
        node_v->parent = node_u->parent;
    }

    void deepCopy(const RBNode* other, RBNode* node, const RBNode* nil) {
        if (other == nil) {
            return;
        }
        if (other->left != nil) {
            node->left = new RBNode{other->left->value, other->left->isBlack, nil_, nil_, nullptr};
            node->left->parent = node;
        }
        deepCopy(other->left, node->left, nil);

        if (other->right != nil) {
            ValueType number = other->right->value;
            node->right = new RBNode{number, other->right->isBlack, nil_, nil_, nullptr};
            node->right->parent = node;
        }
        deepCopy(other->right, node->right, nil);
    }

    void fill(ValueType* nodes, RBNode* node, int* index) const {
        if (node == nil_) {
            return;
        }

        fill(nodes, node->left, index);
        nodes[*index] = node->value;
        (*index)++;
        fill(nodes, node->right, index);
    }
};