#include <iostream>
#include <iterator>
#include <memory>
#include <vector>
#include <random>

std::mt19937 generator(1991304);
std::uniform_int_distribution dist(0, 2000000000);

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;
    int priority = dist(generator);
    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 Split(Node<ValueType>* tree, const ValueType& value, Node<ValueType>*& left_tree,
               Node<ValueType>*& right_tree) {
        if (!tree)
            left_tree = right_tree = nullptr;
        else if (value < tree->value) {
            Split(tree->left, value, left_tree, tree->left);
            if (tree->left) {
                tree->left->parent = tree;
            }
            right_tree = tree;
        } else {
            Split(tree->right, value, tree->right, right_tree);
            if (tree->right) {
                tree->right->parent = tree;
            }
            left_tree = tree;
        }
    }

    void Insert(Node<ValueType>*& cur_tree, Node<ValueType>* new_node) {
        if (!cur_tree) {
            cur_tree = new_node;
            ++size_;
        } else if (!(cur_tree->value < new_node->value) && !(new_node->value < cur_tree->value)) {
            return;
        } else if (cur_tree->priority < new_node->priority) {
            auto parent = cur_tree->parent;
            Split(cur_tree, new_node->value, new_node->left, new_node->right);
            cur_tree = new_node;
            ++size_;
            if (new_node->left) {
                new_node->left->parent = new_node;
            }
            if (new_node->right) {
                new_node->right->parent = new_node;
            }
            new_node->parent = parent;
        } else {
            if (new_node->value < cur_tree->value) {
                if (!cur_tree->left) {
                    new_node->parent = cur_tree;
                }
                Insert(cur_tree->left, new_node);
            } else {
                if (!cur_tree->right) {
                    new_node->parent = cur_tree;
                }
                Insert(cur_tree->right, new_node);
            }
        }
    }

    void Merge(Node<ValueType>*& return_tree, Node<ValueType>* left_tree,
               Node<ValueType>* right_tree) {
        if (!left_tree || !right_tree) {
            return_tree = left_tree ? left_tree : right_tree;
        } else if (left_tree->priority > right_tree->priority) {
            Merge(left_tree->right, left_tree->right, right_tree);
            return_tree = left_tree;

            if (left_tree->left) {
                left_tree->left->parent = left_tree;
            }

            if (left_tree->right) {
                left_tree->right->parent = left_tree;
            }

        } else {
            Merge(right_tree->left, left_tree, right_tree->left);
            return_tree = right_tree;
            if (right_tree->left) {
                right_tree->left->parent = right_tree;
            }

            if (right_tree->right) {
                right_tree->right->parent = right_tree;
            }
        }
    }

    void Erase(Node<ValueType>*& return_tree, const ValueType& value) {
        if (!return_tree) {
            return;
        }
        if (!(return_tree->value < value) && !(value < return_tree->value)) {
            auto parent = return_tree->parent;
            Merge(return_tree, return_tree->left, return_tree->right);
            --size_;
            if (return_tree) {
                return_tree->parent = parent;
            }
        } else {
            Erase(value < return_tree->value ? return_tree->left : return_tree->right, value);
        }
    }

    Node<ValueType>* DeepCopy(Node<ValueType>* cur) {
        auto new_cur = GetNewNode();
        new_cur->value = cur->value;
        new_cur->priority = cur->priority;

        if (!(new_cur->value < begin_->value) && !(begin_->value < new_cur->value)) {
            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;
    }

    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);
        };
    }

    Node<ValueType>* GetNewNode() {
        if (pool_index == 20000) {
            pool_counter++;
            object_pools_[pool_counter].resize(20000);
            pool_index = 0;
        }

        return object_pools_[pool_counter].data() + pool_index++;
    }

    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;
    size_t pool_index = 0;
    std::vector<std::vector<Node<ValueType>>> object_pools_ =
        std::vector<std::vector<Node<ValueType>>>(100);

public:
    typedef SetIterator<ValueType> iterator;

    Set() {
        object_pools_[0].resize(20000);
    }

    template <typename ForwardIT>
    Set(ForwardIT begin, ForwardIT end) {
        object_pools_[0].resize(20000);
        for (auto it = begin; it != end; ++it) {
            insert(*it);
        }
    }

    explicit Set(std::initializer_list<ValueType> ilist) {
        object_pools_[0].resize(20000);
        for (const auto& elem : ilist) {
            insert(elem);
        }
    }

    Set(const Set& other) {
        object_pools_[0].resize(20000);
        if (other.size_ == 0) {
            return;
        }

        begin_ = GetNewNode();
        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;
        }

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

            return *this;
        }

        begin_ = GetNewNode();
        begin_->value = other.begin_->value;
        root_ = DeepCopy(other.root_);

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

        size_ = other.size_;
        return *this;
    }

    ~Set() {
        if (end_) {
            delete end_;
        }
    }

    size_t size() const {
        return size_;
    }

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

    void insert(const ValueType& value) {
        Node<ValueType>* new_node = GetNewNode();
        new_node->value = value;

        Insert(root_, new_node);

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

        if (begin_ == end_) {
            begin_ = new_node;
        }

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

    void erase(const ValueType& value) {
        if (size_ == 0) {
            return;
        }

        if (!(begin_->value < value) && (value < begin_->value)) {
            auto iter = SetIterator{begin_};
            ++iter;
            begin_ = iter.node;
        }

        Erase(root_, value);
    }

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

        Node<ValueType>* cur_node = root_;

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

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

            if (child) {
                cur_node = child;
            } else {
                return SetIterator{end_};
            }
        }

        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_};
    }
};