class treap{
private:
    struct node{
        int val, prior, sz;

        int l;
        int r;

        node(int val){
            this -> val = val;
            this -> prior = gen() % (int)1e9;
            this -> l = -1;
            this -> r = -1;
            this -> sz = 1;
        }
    };

    int root = -1;

    vector < node > t;

    void update(int pos){
        if (pos == -1)return;
        t[pos].sz = 1;
        if (t[pos].l != -1)t[pos].sz += t[t[pos].l].sz;
        if (t[pos].r != -1)t[pos].sz += t[t[pos].r].sz;
    }

    pair < int, int > split_val(int pos, int val){
        if (pos == -1)return {-1, -1};
        if (t[pos].val <= val){
            pair < int, int > p = split_val(t[pos].r, val);
            t[pos].r = p.F;
            update(pos);
            return {pos, p.S};
        }else{
            pair < int, int > p = split_val(t[pos].l, val);
            t[pos].l = p.S;
            update(pos);
            return {p.F, pos};
        }
    }

    int merg(int pos_1, int pos_2){
        if (pos_1 == -1)return pos_2;
        if (pos_2 == -1)return pos_1;
        if (t[pos_1].prior > t[pos_2].prior){
            t[pos_1].r = merg(t[pos_1].r, pos_2);
            update(pos_1);
            return pos_1;
        }else{
            t[pos_2].l = merg(pos_1, t[pos_2].l);
            update(pos_2);
            return pos_2;
        }
    }

    bool find_val(int pos, int val){
        if (pos == -1)return 0;
        if (t[pos].val == val)return 1;
        if (t[pos].val > val)return find_val(t[pos].l, val);
        else return find_val(t[pos].r, val);
    }

    int insert_val(int pos, int new_pos){
        if (pos == -1)return new_pos;
        if (t[pos].prior > t[new_pos].prior){
            if (t[pos].val > t[new_pos].val) t[pos].l = insert_val(t[pos].l, new_pos);
            else t[pos].r = insert_val(t[pos].r, new_pos);
            update(pos);
            return pos;
        }else{
            pair < int, int > p = split_val(pos, t[new_pos].val);
            t[new_pos].l = p.F;
            t[new_pos].r = p.S;
            update(new_pos);
            return new_pos;
        }
    }

    int eras(int pos, int val){
        if (t[pos].val == val) pos = merg(t[pos].l, t[pos].r);
        else if (t[pos].val < val) t[pos].r = eras(t[pos].r, val);
        else t[pos].l = eras(t[pos].l, val);
        update(pos);
        return pos;
    }

    int get(int pos, int indx){
        if (pos == -1)return -1;
        int lft_sz = (t[pos].l == -1 ? 0 : t[t[pos].l].sz);
        if (lft_sz == indx)return t[pos].val;
        if (indx >= lft_sz) return get(t[pos].r, indx - lft_sz - 1);
        else return get(t[pos].l, indx);
    }

public:

    void add(int val){
        if (find_val(root, val))return;
        t.emplace_back(node(val));
        if (root == -1){
            root = t.size() - 1;
            return;
        }
        root = insert_val(root, t.size() - 1);
    }

    void remov(int val){
        (t[root].sz == 1 ? root = -1 : root = eras(root, val));
    }

    int get(int k){
        return get(root, k);
    }
};