1
#include <iostream>
2
#include <memory>
3
#include <vector>
4
#include <array>
5
#include <cassert>
6

7
template <typename Tp>
8
using OwnPtr = std::unique_ptr<Tp>;
9
template <typename Tp>
10
using RefPtr = Tp*;
11

12
class Splay {
13
private:
14
    struct Node {
15
        std::array<RefPtr<Node>, 2> son{nullptr, nullptr};
16
        RefPtr<Node> fat = nullptr;
17
        int cnt = 0, val = 0, sz = 0;
18
    };
19
    std::vector<OwnPtr<Node>> pool;
20

21
    auto dir(RefPtr<Node> x) -> int {
22
        assert(x && x->fat);
23
        return x == x->fat->son[1];
24
    }
25
    void pushUp(RefPtr<Node> x) {
26
        x->sz = x->cnt;
27
        if (x->son[0]) x->sz += x->son[0]->sz;
28
        if (x->son[1]) x->sz += x->son[1]->sz;
29
    }
30
    auto newNode(int v, RefPtr<Node> fat = nullptr) -> RefPtr<Node> {
31
        pool.push_back(std::make_unique<Node>());
32
        auto p = pool.back().get();
33
        p->fat = fat, p->val = v, p->cnt = p->sz = 1;
34
        return p;
35
    }
36

37
    void rotate(RefPtr<Node> x) {
38
        auto y = x->fat;
39
        auto z = y->fat;
40
        int r = dir(x);
41
        int d = z ? dir(y) : 0;
42
        y->son[r] = x->son[!r];
43
        if (x->son[!r]) x->son[!r]->fat = y;
44
        x->son[!r] = y;
45
        if (z) z->son[d] = x;
46
        else rt = x;
47
        y->fat = x;
48
        x->fat = z;
49
        pushUp(y);
50
        pushUp(x);
51
    }
52

53
    void splay(RefPtr<Node> x) {
54
        if (!x) return ;
55
        while (x->fat) {
56
            auto y = x->fat;
57
            auto z = y->fat;
58
            if (z) {
59
                if (dir(x) == dir(y)) rotate(y);
60
                else rotate(x);
61
            }
62
            rotate(x);
63
        }
64
        rt = x;
65
    }
66

67
    void find(int v) {
68
        auto x = rt;
69
        auto y = (RefPtr<Node>)nullptr;
70
        for (; x && x->val != v; y = x, x = x->son[v > x->val]);
71
        splay(x ? x : y);
72
    }
73

74
    void loc(int k) {
75
        auto x = rt;
76
        while (x) {
77
            int ls = x->son[0] ? x->son[0]->sz : 0;
78
            if (k <= ls) {
79
                x = x->son[0];
80
            } else if (k <= ls + x->cnt) {
81
                break;
82
            } else {
83
                k -= ls + x->cnt;
84
                x = x->son[1];
85
            }
86
        }
87
        if (x) splay(x);
88
    }
89

90
    auto merge(RefPtr<Node> x, RefPtr<Node> y) -> RefPtr<Node> {
91
        if (!x || !y) {
92
            if (x) return x;
93
            return y;
94
        }
95
        rt = y;
96
        loc(1);
97
        rt->son[0] = x;
98
        x->fat = rt;
99
        pushUp(rt);
100
        return rt;
101
    }
102

103
public:
104
    RefPtr<Node> rt = nullptr;
105

106
    Splay() = default;
107
    ~Splay() {
108
        clear();
109
    }
110
    void clear() {
111
        rt = nullptr;
112
        std::vector<OwnPtr<Node>>().swap(pool);
113
    }
114

115
    void insert(int v) {
116
        auto x = rt, y = static_cast<RefPtr<Node>>(nullptr);
117
        for (; x && x->val != v; y = x, x = x->son[v > x->val]);
118
        if (x) x->cnt++, x->sz++;
119
        else {
120
            x = newNode(v, y);
121
            if (y) y->son[v > y->val] = x;
122
            else rt = x;
123
        }
124
        splay(x);
125
    }
126

127
    bool remove(int v) {
128
        find(v);
129
        if (!rt || rt->val != v) return false;
130
        rt->cnt--, rt->sz--;
131
        if (!rt->cnt) {
132
            auto x = rt->son[0];
133
            auto y = rt->son[1];
134
            if (x) x->fat = nullptr;
135
            if (y) y->fat = nullptr;
136
            rt = merge(x, y);
137
        }
138
        return true;
139
    }
140

141
    int find_rank(int v) {
142
        find(v);
143
        if (!rt) return 1;
144
        return (rt->son[0] ? rt->son[0]->sz : 0) + (rt->val < v ? rt->cnt : 0) + 1;
145
    }
146

147
    int find_kth(int k) {
148
        if (!rt || k <= 0 || k > rt->sz) return -1;
149
        loc(k);
150
        return rt->val;
151
    }
152

153
    int find_prev(int v) {
154
        find(v);
155
        if (!rt) return -1;
156
        if (rt->val < v) return rt->val;
157
        auto x = rt->son[0];
158
        if (!x) return -1;
159
        for (; x->son[1]; x = x->son[1]);
160
        splay(x);
161
        return rt->val;
162
    }
163

164
    int find_next(int v) {
165
        find(v);
166
        if (!rt) return -1;
167
        if (rt->val > v) return rt->val;
168
        auto x = rt->son[1];
169
        if (!x) return -1;
170
        for (; x->son[0]; x = x->son[0]);
171
        splay(x);
172
        return rt->val;
173
    }
174
};
175

176
auto main() -> int {
177
    int T;
178
    std::cin >> T;
179
    Splay splay;
180
    while (T--) {
181
        int op, x;
182
        std::cin >> op >> x;
183
        switch (op) {
184
            case 1:
185
                splay.insert(x);
186
                break;
187
            case 2:
188
                splay.remove(x);
189
                break;
190
            case 3:
191
                std::cout << splay.find_rank(x) << '\n';
192
                break;
193
            case 4:
194
                std::cout << splay.find_kth(x) << '\n';
195
                break;
196
            case 5:
197
                std::cout << splay.find_prev(x) << '\n';
198
                break;
199
            case 6:
200
                std::cout << splay.find_next(x) << '\n';
201
                break;
202
        }
203
    }
204
    return 0;
205
}