#include <chrono>
#include <iostream>
#include <iterator>
#include <memory>
#include <vector>
#include <cstdlib>
#include <set>
#include <random>

template <typename ValueType>
struct Node {
    Node() = default;

    Node(Node* left, Node* right, Node* parent, const ValueType& value)
        : left(left), right(right), parent(parent), value(value) {
    }
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;
    ValueType value = ValueType();
};

template <typename ValueType>
class Set;

template <typename ValueType>
class SetIterator : public std::iterator<struct bidirectional_iterator_tag, ValueType, size_t,
                                         ValueType*, ValueType&> {
public:
    friend class Set<ValueType>;
    SetIterator() : node(nullptr) {
    }

    explicit SetIterator(Node<ValueType>* node) : node(node) {
    }

    SetIterator(const SetIterator&) = default;
    SetIterator& operator=(const SetIterator&) = default;

    SetIterator& operator++() {
        if (node->right) {
            node = node->right;
            while (node->left) {
                node = node->left;
            }
        } else {
            while (node->parent->right == node) {
                node = node->parent;
            }
            node = node->parent;
        }

        return *this;
    }

    SetIterator& operator--() {
        if (node->left) {
            node = node->left;
            while (node->right) {
                node = node->right;
            }
        } else {
            while (node->parent->left == node) {
                node = node->parent;
            }
            node = node->parent;
        }

        return *this;
    }

    SetIterator operator++(int) {
        SetIterator<ValueType> result(node);
        ++*this;
        return result;
    }

    SetIterator operator--(int) {
        SetIterator<ValueType> result(node);
        --*this;
        return result;
    }

    bool operator==(SetIterator other) {
        return node == other.node;
    }

    bool operator!=(SetIterator other) {
        return node != other.node;
    }

    const ValueType& operator*() {
        return node->value;
    }

    const ValueType* operator->() {
        return &(node->value);
    }

private:
    Node<ValueType>* node;
};

template <typename ValueType>
class Set {
private:
    void SetRoot(Node<ValueType>* node) {
        root_ = node;
        begin_ = node;
        end_->left = root_;
        root_->parent = end_;
    }

    Node<ValueType>* DeepCopy(Node<ValueType>* cur) {
        //        auto new_cur = new Node<ValueType>(nullptr, nullptr, nullptr, cur->value);
        auto new_cur = object_pool_.data() + pool_counter_++;
        new_cur->value = cur->value;
        if (!(new_cur->value < begin_->value) && !(begin_->value < new_cur->value)) {
            //            delete begin_;
            begin_ = new_cur;
        }

        if (cur->left) {
            new_cur->left = DeepCopy(cur->left);
            new_cur->left->parent = new_cur;
        }

        if (cur->right) {
            new_cur->right = DeepCopy(cur->right);
            new_cur->right->parent = new_cur;
        }

        return new_cur;
    }

    void ZigZig(Node<ValueType>* node) const {
        auto parent = node->parent;
        auto grand_parent = parent->parent;
        auto grand_grand_parent = grand_parent->parent;

        bool is_root = root_ == grand_parent;

        parent->parent = grand_parent->parent;
        if (grand_grand_parent->left == grand_parent) {
            grand_grand_parent->left = parent;
        } else {
            grand_grand_parent->right = parent;
        }

        grand_parent->left = parent->right;
        if (parent->right) {
            parent->right->parent = grand_parent;
        }

        grand_parent->parent = parent;
        parent->right = grand_parent;

        if (is_root) {
            const_cast<Set<ValueType>*>(this)->root_ = parent;
        }
    }

    void ZagZag(Node<ValueType>* node) const {
        auto parent = node->parent;
        auto grand_parent = parent->parent;
        auto grand_grand_parent = grand_parent->parent;

        bool is_root = grand_parent == root_;

        parent->parent = grand_parent->parent;
        if (grand_grand_parent->left == grand_parent) {
            grand_grand_parent->left = parent;
        } else {
            grand_grand_parent->right = parent;
        }

        grand_parent->right = parent->left;
        if (parent->left) {
            parent->left->parent = grand_parent;
        }

        grand_parent->parent = parent;
        parent->left = grand_parent;

        if (is_root) {
            const_cast<Set<ValueType>*>(this)->root_ = parent;
        }
    }

    void ZagZig(Node<ValueType>* node) const {
        auto parent = node->parent;

        parent->parent->left = node;
        node->parent = parent->parent;

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

        node->left = parent;
        parent->parent = node;

        ZigZig(parent);
    }

    void ZigZag(Node<ValueType>* node) const {
        auto parent = node->parent;

        parent->parent->right = node;
        node->parent = parent->parent;

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

        parent->parent = node;
        node->right = parent;

        ZagZag(parent);
    }

    void Zig(Node<ValueType>* node) const {
        auto parent = node->parent;

        parent->parent->left = node;
        node->parent = parent->parent;

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

        node->right = parent;
        parent->parent = node;

        const_cast<Set<ValueType>*>(this)->root_ = node;
    }

    void Zag(Node<ValueType>* node) const {
        auto parent = node->parent;

        parent->parent->left = node;
        node->parent = parent->parent;

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

        node->left = parent;
        parent->parent = node;

        const_cast<Set<ValueType>*>(this)->root_ = node;
    }

    void SplayNode(Node<ValueType>* node) const {
        while (node != root_) {
            if (node->parent == root_) {
                if (root_->left == node) {
                    Zig(node);
                } else {
                    Zag(node);
                }
                continue;
            }

            auto parent = node->parent;
            bool is_left_child = node->parent->left == node;
            bool is_parent_left_child = parent->parent->left == parent;

            if (is_parent_left_child) {
                if (is_left_child) {
                    ZigZig(node);
                } else {
                    ZagZig(node);
                }
            } else {
                if (is_left_child) {
                    ZigZag(node);
                } else {
                    ZagZag(node);
                }
            }
        }
    }

    SetIterator<ValueType> LowerBound(Node<ValueType>* node, const ValueType& value) const {
        if (!(value < node->value) && !(node->value < value)) {
            return SetIterator{node};
        }

        auto child = node;

        bool is_left = true;

        if (value < node->value) {
            is_left = true;
            child = node->left;
        } else {
            is_left = false;
            child = node->right;
        }

        if (!child) {
            if (is_left) {
                return SetIterator{node};
            } else {
                auto iter = SetIterator<ValueType>(node);
                ++iter;
                return iter;
            }
        } else {
            return LowerBound(child, value);
        };
    }

    void Delete(Node<ValueType>* cur) {
        if (cur->left) {
            Delete(cur->left);
        }

        if (cur->right) {
            Delete(cur->right);
        }

        delete cur;
    }

    Node<ValueType>* root_ = nullptr;
    Node<ValueType>* end_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
    Node<ValueType>* begin_ = end_;
    size_t size_ = 0;
    size_t pool_counter_ = 0;
    std::vector<Node<ValueType>> object_pool_ =
        std::vector<Node<ValueType>>(1000000 / sizeof(ValueType));

public:
    typedef SetIterator<ValueType> iterator;

    Set() {
    }

    template <typename ForwardIT>
    Set(ForwardIT begin, ForwardIT end) {
        for (auto it = begin; it != end; ++it) {
            insert(*it);
        }
    }

    explicit Set(std::initializer_list<ValueType> ilist) {
        for (const auto& elem : ilist) {
            insert(elem);
        }
    }

    Set(const Set& other) {
        if (other.size_ == 0) {
            return;
        }

        //        begin_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
        begin_ = object_pool_.data() + pool_counter_++;
        begin_->value = other.begin_->value;
        root_ = DeepCopy(other.root_);

        end_->left = root_;
        root_->parent = end_;

        size_ = other.size_;
    }

    Set& operator=(const Set& other) {
        if (this == &other) {
            return *this;
        }

        //        this->~Set();
        //        end_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
        //        end_ = object_pool_.data() + pool_counter_++;

        if (other.size_ == 0) {
            size_ = 0;
            root_ = nullptr;
            begin_ = end_;
            end_->left = root_;

            return *this;
        }

        //        begin_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
        begin_ = object_pool_.data() + pool_counter_++;
        begin_->value = other.begin_->value;
        root_ = DeepCopy(other.root_);

        end_->left = root_;
        root_->parent = end_;

        size_ = other.size_;
        return *this;
    }

    ~Set() {
        //        if (end_) {
        //            std::vector<Node<ValueType>*> nodes(size_);
        //            int counter = 0;
        //            for (auto iter = begin(); iter != end(); ++iter) {
        //                nodes[counter] = iter.node;
        //                ++counter;
        //            }
        //
        //            for (size_t i = 0; i < nodes.size(); ++i) {
        //                delete nodes[i];
        //            }
        //
        //            delete end_;
        //        }
        if (end_) {
            delete end_;
        }
    }

    size_t size() const {
        return size_;
    }

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

    void insert(const ValueType& value) {
        //        auto node = new Node<ValueType>(nullptr, nullptr, nullptr, value);
        auto node = object_pool_.data() + pool_counter_++;
        node->value = value;

        if (!root_) {
            SetRoot(node);
            ++size_;
            return;
        }

        find(value);

        if (!(root_->value < value) && !(value < root_->value)) {
            //            delete node;
            return;
        }

        if (value < root_->value) {
            node->right = root_;
            root_->parent = node;

            if (root_->left) {
                node->left = root_->left;
                root_->left->parent = node;
                root_->left = nullptr;
            }
        } else {
            node->left = root_;
            root_->parent = node;

            if (root_->right) {
                node->right = root_->right;
                root_->right->parent = node;
                root_->right = nullptr;
            }
        }

        node->parent = end_;
        end_->left = node;
        root_ = node;

        if (node->value < begin_->value) {
            begin_ = node;
        }

        ++size_;
    }

    void erase(const ValueType& value) {
        if (!root_) {
            return;
        }

        find(value);

        if ((root_->value < value) || (value < root_->value)) {
            return;
        }

        if (begin_ == root_) {
            auto iter = SetIterator<ValueType>(root_);
            ++iter;
            begin_ = iter.node;
        }

        if (!root_->left) {
            //            auto old_root = root_;
            end_->left = root_->right;

            if (root_->right) {
                root_->right->parent = root_->parent;
                root_ = root_->right;
            } else {
                root_ = nullptr;
            }

            //            delete old_root;
            --size_;
            return;
        }

        auto right_tree = root_->right;

        //        Node<ValueType>* old_root = root_;
        root_ = root_->left;
        find(value);

        root_->right = right_tree;
        if (right_tree) {
            right_tree->parent = root_;
        }
        end_->left = root_;
        root_->parent = end_;
        --size_;
        //        delete old_root;
    }

    SetIterator<ValueType> find(const ValueType& value) const {
        if (size_ == 0) {
            return SetIterator{end_};
        }

        int depth = 0;

        Node<ValueType>* node = root_;

        while (node) {
            if (!(node->value < value) && !(value < node->value)) {
                SplayNode(node);
                return SetIterator(node);
            }

            Node<ValueType>* child = nullptr;
            if (node->value < value) {
                child = node->right;
            } else {
                child = node->left;
            }

            if (!child) {
                SplayNode(node);
                return SetIterator{end_};
            } else {
                node = child;
            }

            ++depth;
        }

        return SetIterator{end_};
    }

    SetIterator<ValueType> lower_bound(const ValueType& value) const {
        if (size_ == 0) {
            return SetIterator{end_};
        }

        return LowerBound(root_, value);
    }

    SetIterator<ValueType> begin() const {
        return SetIterator{begin_};
    }

    SetIterator<ValueType> end() const {
        return SetIterator{end_};
    }
};

std::ostream& operator<<(std::ostream& os, const std::vector<int> vec) {
    for (auto elem : vec) {
        os << elem;
    }

    return os;
}

void TestInsert() {
    std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> shuffled = sorted;

    while (std::next_permutation(shuffled.begin(), shuffled.end())) {
        Set<int> s(shuffled.begin(), shuffled.end());
        std::vector<int> from_set;
        for (auto elem : s) {
            from_set.push_back(elem);
        }

        if (from_set != sorted) {
            std::cout << shuffled;
            exit(0);
        }
    }
}

void TestFind() {
    Set<int> s{1, 6, 3, 8, 2, 4, 7, 5};
    auto iter = s.find(1);
    assert(*iter == 1);
    assert(iter == s.begin());
    assert(iter != s.end());

    iter = s.find(9);
    assert(iter == s.end());
    assert(iter != s.begin());
}

void TestErase() {
    Set<int> s{1, 6, 3, 8, 2, 4, 7, 5};

    for (int i = 0; i <= 9; ++i) {
        s.erase(i);
        assert(s.find(i) == s.end());
    }

    assert(s.empty());

    s = Set{1, 6, 3, 8, 2, 4, 7, 5};

    s.erase(9u);
    assert(s.size() == 8u);
    s.erase(4);
    s.erase(4);
    s.erase(4);
    assert(s.size() == 7u);
}

void TestLowerBound() {
    Set<int> s = Set{1, 5, 6, 9, 12};

    std::vector<int> ans = {1, 1, 5, 5, 5, 5, 6, 9, 9, 9, 12, 12, 12};
    for (int i = 0; i <= 12; ++i) {
        auto iter = s.lower_bound(i);
        assert(*iter == ans[i]);
    }

    assert(s.lower_bound(13) == s.end());
}

void TestBig() {
    Set<int> s;
    std::vector<int> vec;

    for (int i = 0; i < 1000000; ++i) {
        vec.push_back(i);
    }

    std::shuffle(vec.begin(), vec.end(), std::mt19937());

    for (auto i : vec) {
        s.insert(i);
    }

    std::shuffle(vec.begin(), vec.end(), std::mt19937());

    for (int i = 0; i < 1000000; ++i) {
        s.find(vec[i]);
    }

    std::shuffle(vec.begin(), vec.end(), std::mt19937());

    for (int i = 0; i < 1000000; ++i) {
        s.erase(vec[i]);
    }
}

int main() {
    TestLowerBound();
    TestInsert();
    TestErase();
    TestFind();
    TestBig();

    return 0;
}