#include <iostream>
#include <vector>
#include <utility>
#include <memory>
using namespace std;

template<typename Type>
struct Node {
    Type key;
    shared_ptr<Node <Type>> parent, l_son, r_son;

    Node() {}

    Node(const Node &other): key(other.key),
                             parent(nullptr),
                             l_son(nullptr),
                             r_son(nullptr) {}

    Node(const Type &key) : key(key),
                            parent(nullptr),
                            l_son(nullptr),
                            r_son(nullptr) {}

    Node(const Type &key, shared_ptr<Node> l_son, shared_ptr<Node> r_son) : key(key),
                                                                            parent(nullptr),
                                                                            l_son(l_son),
                                                                            r_son(r_son) {}
    ~Node() {}

    friend ostream &operator<<(ostream &stream, Node<Type> &node) {
        stream << node << ": " << "key = " << node.key
               << " l_son = " << node.l_son << " r_son = "
               << node.r_son << " parent = " << node.parent << endl;

        return stream;
    }
};

template<typename Type>
class NodeIterator {
 private:
    const Node <Type> *p, *root;

 public:
    NodeIterator(): p(nullptr), root(nullptr) {}

    NodeIterator(shared_ptr<const Node <Type>> p,
                 shared_ptr<const Node <Type>> root): p(p.get()), root(root.get()) {}

    NodeIterator(shared_ptr<const Node<Type>> root): root(root.get()) {
        p = this->root;
        while (p != nullptr && p->l_son != nullptr) {
            p = p->l_son.get();
        }
    }

    NodeIterator(const NodeIterator &other): p(other.p), root(other.root) {}

    NodeIterator &operator=(const NodeIterator &other) {
        p = other.p;
        root = other.root;
        return *this;
    }

    ~NodeIterator() {
    }

    const Type &operator*() const {
        return p->key;
    }

    const Type *operator->() const {
        return &(p->key);
    }

    bool operator==(const NodeIterator<Type> &other) const {
        return (p == other.p && root == other.root);
    }

    bool operator!=(const NodeIterator<Type> &other) const {
        return !(p == other.p && root == other.root);
    }

    NodeIterator &operator++() {
        if (p == nullptr) {
            return *this;
        }

        if (p->r_son != nullptr) {
            p = p->r_son.get();
        } else {
            while (p->parent != nullptr && p->parent->r_son.get() == p) {
                p = p->parent.get();
            }
            p = p->parent.get();

            return *this;
        }

        while (p->l_son != nullptr) {
            p = p->l_son.get();
        }

        return *this;
    }

    NodeIterator operator++(int) {
        auto res = *this;
        ++*this;

        return res;
    }

    NodeIterator &operator--() {
        if (p == nullptr) {
            p = root;
            if (p == nullptr) {
                return *this;
            }

            while (p->r_son != nullptr) {
                p = p->r_son.get();
            }

            return *this;
        }

        if (p->l_son != nullptr) {
            p = p->l_son.get();
            while (p->r_son != nullptr) {
                p = p->r_son.get();
            }

            return *this;
        }

        while (p->parent != nullptr && p->parent->l_son.get() == p) {
            p = p->parent.get();
        }
        p = p->parent.get();

        return *this;
    }

    NodeIterator operator--(int) {
        auto res = *this;
        --*this;

        return res;
    }
};

template<typename Type>
class Set {
    typedef NodeIterator<Type> iterator;
 private:
    int cnt;
    shared_ptr<Node <Type>> root;
    iterator begin_iterator;

 public:

    // Constuctors
    Set(): cnt(0),
           root(nullptr) {}

    template <class TIterator>
    Set(TIterator first, TIterator last): Set() {
        while (first != last) {
            insert(*first++);
        }
    }

    Set(std::initializer_list<Type> data): Set() {
        for (auto x : data) {
            insert(x);
        }
    }

    Set(const Set<Type> &other) {
        cnt = other.cnt;
        root = copy_tree(other.root);
    }

    ~Set() {
        delete_tree(root);
    }

    Set<Type> &operator=(const Set<Type> &other) {
        cnt = other.cnt;
        delete_tree(root);
        root = copy_tree(other.root);

        return *this;
    }

    void update_min() {
        if (root == nullptr) {
            return;
        }

        auto p = root;
        while (p->l_son != nullptr) {
            p = p->l_son;
        }

        root = splay(p);
    }

    void update_max() {
        if (root == nullptr) {
            return;
        }

        auto p = root;
        while (p->r_son != nullptr) {
            p = p->r_son;
        }

        root = splay(p);
    }

    bool equal(const Type &key1, const Type &key2) const {
        return !(key1 < key2 || key2 < key1);
    }

    bool bigger(const Type &key1, const Type &key2) const {
        return (key2 < key1);
    }

    void delete_tree(shared_ptr<Node <Type>> &v) {
        if (v == nullptr) {
            return;
        }

        delete_tree(v->l_son);
        delete_tree(v->r_son);

        v->parent = nullptr;
    }

    shared_ptr<Node <Type>> copy_tree(const shared_ptr<Node <Type>> &v) {
        if (v == nullptr) {
            return nullptr;
        }

        shared_ptr<Node <Type>> new_v(new Node<Type>(v->key));
        new_v->l_son = copy_tree(v->l_son);
        new_v->r_son = copy_tree(v->r_son);

        keep_parent(new_v);

        return new_v;
    }

    void print(const shared_ptr<Node <Type>> node) const {
        if (node == nullptr) {
            return;
        }

        print(node->l_son);

        cout << node << ": " << "key = " << node->key
             << " l_son = " << node->l_son << " r_son = "
             << node->r_son << " parent = " << node->parent << endl;

        print(node->r_son);
    }

    shared_ptr<Node <Type>> find(shared_ptr<Node <Type>> node, const Type &key) {
        while (true) {
            if (node == nullptr) {
                return node;
            }

            if (equal(node->key, key)) {
                return splay(node);
            }

            if (bigger(node->key, key) && node->l_son != nullptr) {
                node = node->l_son;
            } else if (node->key < key && node->r_son != nullptr) {
                node = node->r_son;
            } else {
                return splay(node);
            }
        }
    }

    shared_ptr<Node <Type>> insert(shared_ptr<Node <Type>> root, const Type &key) {
        auto sons = split(root, key);
        shared_ptr<Node <Type>> new_root(new Node<Type>(key, sons.first, sons.second));
        keep_parent(new_root);

        return new_root;
    }

    shared_ptr<Node <Type>> remove(shared_ptr<Node <Type>> root, const Type &key) {
        root = find(root, key);

        if (root->key != key) {
            return root;
        }

        set_parent(root->l_son, nullptr);
        set_parent(root->r_son, nullptr);

        return merge(root->l_son, root->r_son);
    }

    void print_once(const shared_ptr<Node <Type>> node) const {
        if (node == nullptr) {
            cout << "nullptr" << endl;
            return;
        }

        cout << node << ": " << "key = " << node->key
             << " l_son = " << node->l_son << " r_son = "
             << node->r_son << " parent = " << node->parent << endl;
    }

    void set_parent(shared_ptr<Node <Type>> child, shared_ptr<Node <Type>> parent) {
        if (child == nullptr) {
            return;
        }

        child->parent = parent;
    }

    void keep_parent(shared_ptr<Node <Type>> node) {
        if (node == nullptr) {
            return;
        }

        set_parent(node->l_son, node);
        set_parent(node->r_son, node);
    }

    void rotate(shared_ptr<Node <Type>> child, shared_ptr<Node <Type>> parent) {
        shared_ptr<Node <Type>> gparent = parent->parent;
        if (gparent != nullptr) {
            if (gparent->l_son == parent) {
                gparent->l_son = child;
            } else {
                gparent->r_son = child;
            }
        }

        if (parent->l_son == child) {
            parent->l_son = child->r_son;
            child->r_son = parent;
        } else {
            parent->r_son = child->l_son;
            child->l_son = parent;
        }

        keep_parent(child);
        keep_parent(parent);
        child->parent = gparent;
    }

    shared_ptr<Node <Type>> splay(shared_ptr<Node <Type>> child) {
        while (true) {
            if (child->parent == nullptr) {
                return child;
            }

            auto parent = child->parent;
            auto gparent = parent->parent;

            if (gparent == nullptr) {
                rotate(child, parent);
                return child;
            }

            bool zigzig = ((gparent->l_son == parent) == (parent->l_son == child));
            if (zigzig) {
                rotate(parent, gparent);
                rotate(child, parent);
            } else {
                rotate(child, parent);
                rotate(child, gparent);
            }
        }
    }

    pair<shared_ptr<Node <Type>>, shared_ptr<Node <Type>>>
    split(shared_ptr<Node <Type>> root, const Type &key) {
        if (root == nullptr) {
            return make_pair(root, root);
        }

        root = find(root, key);
        if (equal(root->key, key)) {
            set_parent(root->l_son, nullptr);
            set_parent(root->r_son, nullptr);

            return make_pair(root->l_son, root->r_son);
        }

        if (root->key < key) {
            auto r_son = root->r_son;
            root->r_son = nullptr;
            set_parent(r_son, nullptr);
            return make_pair(root, r_son);
        }

        auto l_son = root->l_son;
        root->l_son = nullptr;
        set_parent(l_son, nullptr);
        return make_pair(l_son, root);
    }

    shared_ptr<Node <Type>> merge(shared_ptr<Node <Type>> left, shared_ptr<Node <Type>> right) {
        if (left == nullptr) {
            return right;
        }
        if (right == nullptr) {
            return left;
        }

        right = find(right, left->key);
        right->l_son = left;
        left->parent = right;
        return right;
    }

    // interface

    void print() const {
        if (root == nullptr) {
            cout << "empty" << endl;
        } else {
            print(root);
        }
    }

    iterator find(const Type &key) const {
        shared_ptr<Node <Type>> p = root;

        while (p != nullptr && !equal(p->key, key)) {
            if (bigger(p->key, key)) {
                p = p->l_son;
            } else {
                p = p->r_son;
            }
        }

        if (p == nullptr) {
            return end();
        }
        return iterator(p, root);
    }

    iterator lower_bound(const Type &key) const {
        return lower_bound(root, key);
    }

    iterator lower_bound(shared_ptr<Node <Type>> v, const Type &key) const {
        if (v == nullptr) {
            return end();
        }

        if (v->key < key) {
            return lower_bound(v->r_son, key);
        }

        iterator res(v, root);
        iterator res1 = lower_bound(v->l_son, key);
        if (res1 != end() && *res1 < *res) {
            return res1;
        }
        return res;
    }

    void erase(const Type &key) {
        if (root == nullptr) {
            return;
        }

        root = find(root, key);
        if (root->key == key) {
            root = remove(root, key);
            --cnt;
        }
    }

    void insert(const Type &key) {
        root = find(root, key);

        if (root == nullptr || !equal(root->key, key)) {
            root = insert(root, key);
            ++cnt;
        }
    }

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

    size_t size() const {
        return cnt;
    }

    iterator begin() const {
        return iterator(root);
    }

    iterator end() const {
        return iterator(nullptr, root);
    }
};