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

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

12
class FhqTreap {
13
private:
14
    struct Node {
15
        std::array<RefPtr<Node>, 2> son{nullptr, nullptr};
16
        int cnt = 0, val = 0, sz = 0;
17
        std::uint32_t pri = 0;
18
    };
19

20
    std::vector<OwnPtr<Node>> pool;
21

22
    std::uint32_t seed = 114514;
23

24
    auto rnd() -> std::uint32_t {
25
        seed ^= seed << 13;
26
        seed ^= seed >> 17;
27
        seed ^= seed << 5;
28
        return seed;
29
    }
30

31
    auto size(RefPtr<Node> x) -> int {
32
        return x ? x->sz : 0;
33
    }
34

35
    void pushUp(RefPtr<Node> x) {
36
        if (!x) return;
37
        x->sz = x->cnt + size(x->son[0]) + size(x->son[1]);
38
    }
39

40
    auto newNode(int v) -> RefPtr<Node> {
41
        pool.push_back(std::make_unique<Node>());
42
        auto p = pool.back().get();
43

44
        p->val = v;
45
        p->cnt = p->sz = 1;
46
        p->pri = rnd();
47

48
        return p;
49
    }
50

51
    /*
52
        equal == false:
53
            x: val < v
54
            y: val >= v
55

56
        equal == true:
57
            x: val <= v
58
            y: val > v
59
    */
60
    void split(
61
        RefPtr<Node> p,
62
        int v,
63
        RefPtr<Node>& x,
64
        RefPtr<Node>& y,
65
        bool equal = false
66
    ) {
67
        if (!p) {
68
            x = y = nullptr;
69
            return;
70
        }
71

72
        if (p->val < v || (equal && p->val == v)) {
73
            x = p;
74
            split(p->son[1], v, x->son[1], y, equal);
75
            pushUp(x);
76
        } else {
77
            y = p;
78
            split(p->son[0], v, x, y->son[0], equal);
79
            pushUp(y);
80
        }
81
    }
82

83
    auto merge(RefPtr<Node> x, RefPtr<Node> y) -> RefPtr<Node> {
84
        if (!x || !y) {
85
            return x ? x : y;
86
        }
87

88
        if (x->pri < y->pri) {
89
            x->son[1] = merge(x->son[1], y);
90
            pushUp(x);
91
            return x;
92
        } else {
93
            y->son[0] = merge(x, y->son[0]);
94
            pushUp(y);
95
            return y;
96
        }
97
    }
98

99
    auto kth(RefPtr<Node> x, int k) -> RefPtr<Node> {
100
        while (x) {
101
            int ls = size(x->son[0]);
102

103
            if (k <= ls) {
104
                x = x->son[0];
105
            } else if (k <= ls + x->cnt) {
106
                return x;
107
            } else {
108
                k -= ls + x->cnt;
109
                x = x->son[1];
110
            }
111
        }
112

113
        return nullptr;
114
    }
115

116
    auto rightMost(RefPtr<Node> x) -> RefPtr<Node> {
117
        if (!x) return nullptr;
118
        while (x->son[1]) x = x->son[1];
119
        return x;
120
    }
121

122
    auto leftMost(RefPtr<Node> x) -> RefPtr<Node> {
123
        if (!x) return nullptr;
124
        while (x->son[0]) x = x->son[0];
125
        return x;
126
    }
127

128
public:
129
    RefPtr<Node> rt = nullptr;
130

131
    FhqTreap() = default;
132

133
    ~FhqTreap() {
134
        clear();
135
    }
136

137
    void clear() {
138
        rt = nullptr;
139
        std::vector<OwnPtr<Node>>().swap(pool);
140
        seed = 114514;
141
    }
142

143
    void insert(int v) {
144
        RefPtr<Node> a = nullptr;
145
        RefPtr<Node> b = nullptr;
146
        RefPtr<Node> c = nullptr;
147

148
        split(rt, v, a, b, false); // a < v, b >= v
149
        split(b, v, c, b, true);   // c == v, b > v
150

151
        if (c) {
152
            c->cnt++;
153
            pushUp(c);
154
        } else {
155
            c = newNode(v);
156
        }
157

158
        rt = merge(merge(a, c), b);
159
    }
160

161
    bool remove(int v) {
162
        RefPtr<Node> a = nullptr;
163
        RefPtr<Node> b = nullptr;
164
        RefPtr<Node> c = nullptr;
165

166
        split(rt, v, a, b, false); // a < v, b >= v
167
        split(b, v, c, b, true);   // c == v, b > v
168

169
        if (!c) {
170
            rt = merge(a, b);
171
            return false;
172
        }
173

174
        if (c->cnt > 1) {
175
            c->cnt--;
176
            pushUp(c);
177
        } else {
178
            auto del = c;
179
            c = merge(c->son[0], c->son[1]);
180

181
            del->son[0] = del->son[1] = nullptr;
182
            del->cnt = del->sz = 0;
183
        }
184

185
        rt = merge(merge(a, c), b);
186
        return true;
187
    }
188

189
    int find_rank(int v) {
190
        RefPtr<Node> a = nullptr;
191
        RefPtr<Node> b = nullptr;
192

193
        split(rt, v, a, b, false); // a < v, b >= v
194

195
        int ans = size(a) + 1;
196

197
        rt = merge(a, b);
198
        return ans;
199
    }
200

201
    int find_kth(int k) {
202
        if (!rt || k <= 0 || k > rt->sz) return -1;
203

204
        auto x = kth(rt, k);
205
        return x ? x->val : -1;
206
    }
207

208
    int find_prev(int v) {
209
        RefPtr<Node> a = nullptr;
210
        RefPtr<Node> b = nullptr;
211

212
        split(rt, v, a, b, false); // a < v, b >= v
213

214
        auto x = rightMost(a);
215
        int ans = x ? x->val : -1;
216

217
        rt = merge(a, b);
218
        return ans;
219
    }
220

221
    int find_next(int v) {
222
        RefPtr<Node> a = nullptr;
223
        RefPtr<Node> b = nullptr;
224

225
        split(rt, v, a, b, true); // a <= v, b > v
226

227
        auto x = leftMost(b);
228
        int ans = x ? x->val : -1;
229

230
        rt = merge(a, b);
231
        return ans;
232
    }
233
};
234

235
auto main() -> int {
236
    int T;
237
    std::cin >> T;
238

239
    FhqTreap treap;
240

241
    while (T--) {
242
        int op, x;
243
        std::cin >> op >> x;
244

245
        switch (op) {
246
            case 1:
247
                treap.insert(x);
248
                break;
249
            case 2:
250
                treap.remove(x);
251
                break;
252
            case 3:
253
                std::cout << treap.find_rank(x) << '\n';
254
                break;
255
            case 4:
256
                std::cout << treap.find_kth(x) << '\n';
257
                break;
258
            case 5:
259
                std::cout << treap.find_prev(x) << '\n';
260
                break;
261
            case 6:
262
                std::cout << treap.find_next(x) << '\n';
263
                break;
264
        }
265
    }
266

267
    return 0;
268
}