#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

// https://c...content-available-to-author-only...s.com/blog/entry/95575

#define len(a) (ll)a.size()
typedef long long ll;
typedef long double ld;

bool test=false;
ll mod1=1e9+7;
ll mod2=998244353;
ll inf=1e10+5;

enum colour {red, black};

struct Node {

    ll data, size;
    bool colour;
    Node *parent, *left, *right;
};

class RBTree {
public: // added this to gain access to tNil

    Node *root, *tNil;

    Node* findNode(Node *z) {

        Node *x=this->root;

        while(x!=tNil) {

            if(x->data==z->data) {

                return x;
            } else if(z->data<x->data) {

                x=x->left;
            } else {

                x=x->right;
            }
        }

        return tNil;
    }

    Node* findMin(Node *z) {

        while(z->left!=tNil) {

            z=z->left;
        }

        return z;
    }

    void leftRotate(Node *x) {

        if(x->right==tNil) {

            return;
        }

        Node *y=x->right;
        x->right=y->left;

        if(y->left!=tNil) {

            y->left->parent=x;
        }

        y->parent=x->parent;

        if(x->parent==tNil) {

            this->root=y;
        } else if(x==x->parent->left) {

            x->parent->left=y;
        } else {

            x->parent->right=y;
        }

        y->left=x;
        x->parent=y;
        y->size=x->size;
        x->size=x->left->size+x->right->size+1;
    }

    void rightRotate(Node *y) {

        if(y->left==tNil) {

            return;
        }

        Node *x=y->left;
        y->left=x->right;

        if(x->right!=tNil) {

            x->right->parent=y;
        }

        x->parent=y->parent;

        if(y->parent==tNil) {

            this->root=x;
        } else if(y==y->parent->right) {

            y->parent->right=x;
        } else {

            y->parent->left=x;
        }

        x->right=y;
        y->parent=x;
        x->size=y->size;
        y->size=y->left->size+y->right->size+1;
    }

    void insertFixUp(Node *z) {

        while(z->parent->colour==red) {

            if(z->parent==z->parent->parent->left) {

                Node *y=z->parent->parent->right;

                if(y->colour==red) {

                    z->parent->colour=black;
                    y->colour=black;

                    if(z->parent->parent!=this->root) {

                        z->parent->parent->colour=red;
                    }
                    z=z->parent->parent;
                } else {

                    if(z==z->parent->right) {

                        z=z->parent;
                        leftRotate(z);
                    }

                    z->parent->colour=black;
                    z->parent->parent->colour=red;
                    rightRotate(z->parent->parent);
                }
            } else {

                Node *y=z->parent->parent->left;

                if(y->colour==red) {

                    z->parent->colour=black;
                    y->colour=black;

                    if(z->parent->parent!=this->root) {

                        z->parent->parent->colour=red;
                    }
                    z=z->parent->parent;
                } else {

                    if(z==z->parent->left) {

                        z=z->parent;
                        rightRotate(z);
                    }

                    z->parent->colour=black;
                    z->parent->parent->colour=red;
                    leftRotate(z->parent->parent);
                }
            }
        }
    }

    void insertNode(Node *z) {

        if(this->root==tNil) {

            z->colour=black;
            this->root=z;
            this->root->size=1;
            return;
        }

        Node *y=tNil, *x=this->root;

        while(x!=tNil) {

            y=x;
            x->size++;

            if(z->data<x->data) {

                x=x->left;
            } else {

                x=x->right;
            }
        }

        z->parent=y;

        if(z->data<y->data) {

            y->left=z;
        } else {

            y->right=z;
        }

        insertFixUp(z);
    }

    void transplant(Node *u, Node *v) {

        if(u->parent==tNil) {

            this->root=v;
        } else if(u==u->parent->left) {

            u->parent->left=v;
        } else {

            u->parent->right=v;
        }
        v->parent=u->parent;
    }

    void deleteFixUp(Node *x) {

        while(x!=this->root && x->colour==black) {

            if(x==x->parent->left) {

                Node *w=x->parent->right;

                if(w->colour==red) {

                    w->colour=black;
                    x->parent->colour=red;
                    leftRotate(x->parent);

                    w=x->parent->right;
                }

                if(w->left->colour==black && w->right->colour==black) {

                    w->colour=red;
                    x=x->parent;
                } else {

                    if(w->right->colour==black) {

                        w->left->colour=black;
                        w->colour=red;
                        rightRotate(w);

                        w=x->parent->right;
                    }

                    w->colour=x->parent->colour;
                    x->parent->colour=red;
                    w->right->colour=black;
                    leftRotate(x->parent);
                    x=this->root;
                }
            } else {

                Node *w=x->parent->left;

                if(w->colour==red) {

                    w->colour=black;
                    x->parent->colour=red;
                    rightRotate(x->parent);

                    w=x->parent->left;
                }

                if(w->right->colour==black && w->left->colour==black) {

                    w->colour=red;
                    x=x->parent;
                } else {

                    if(w->left->colour==black) {

                        w->right->colour=black;
                        w->colour=red;
                        leftRotate(w);

                        w=x->parent->left;
                    }

                    w->colour=x->parent->colour;
                    x->parent->colour=red;
                    w->left->colour=black;
                    rightRotate(x->parent);
                    x=this->root;
                }
            }
        }
        x->colour=black;
    }

    void deleteNode(Node *z) {

        Node *y=z, *x;
        bool originalColour=y->colour;

        if(z->left==tNil) {

            x=z->right;
            transplant(z, z->right);
        } else if(z->right==tNil) {

            x=z->left;
            transplant(z, z->left);
        } else {

            y=findMin(z->right);
            originalColour=y->colour;

            x=y->right;

            if(y->parent==z) {

                x->parent=y;
            } else {

                transplant(y, y->right);
                y->right=z->right;
                y->right->parent=y;

                Node *s=x->parent;

                while(s!=tNil && s!=y) {

                    s->size--;
                    s=s->parent;
                }
            }

            transplant(z, y);

            y->left=z->left;
            y->left->parent=y;
            y->colour=z->colour;

            y->size=y->left->size+y->right->size+1;
        }

        if(originalColour==black) {

            deleteFixUp(x);
        }
    }

    void inOrderHelper(Node *node) {

        if(node==tNil) {

            return;
        }

        inOrderHelper(node->left);

        std::cout<<node->data<<" ";

        inOrderHelper(node->right);
    }

public:

    RBTree() {

        tNil=new Node();
        tNil->colour=black;
        tNil->size=0;

        tNil->left=tNil;
        tNil->right=tNil;
        tNil->parent=tNil;

        this->root=tNil;
    }

    Node* getRoot() {

        return this->root;
    }

    Node* find(ll key) {

        Node *z=new Node();

        z->data=key;

        return findNode(z);
    }

    void insert(ll key) {

        Node *z=new Node();
        z->data=key;
        z->colour=red;
        z->size=1;

        z->left=tNil;
        z->right=tNil;
        z->parent=tNil;

        insertNode(z);
    }

    void erase(ll key) {

        Node *z=find(key);

        if(z==tNil) {

            return;
        }

        Node *s=z->parent;

        while(s!=tNil) {

            s->size--;
            s=s->parent;
        }

        deleteNode(z);
    }

    ll osSelect(Node *x, ll i) {

        ll r=x->left->size+1;

        if(i==r) {

            return x->data;
        } else if(i<r) {

            return osSelect(x->left, i);
        } else {

            return osSelect(x->right, i-r);
        }
    }

    ll osRank(Node *x) {

        ll r=x->left->size+1;

        Node *y=x;

        while(y!=this->root) {

            if(y==y->parent->right) {

                r+=y->parent->left->size+1;
            }
            y=y->parent;
        }

        return r;
    }

    void inOrder() {

        inOrderHelper(this->root);
    }
};

const int N = 1e6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> input;
clock_t start;
ordered_set st;
RBTree rbt;

void testInsert() {
    uniform_int_distribution<int> uid(1, 1e9);
    set<int> uniq;
    while (uniq.size() < N)
        uniq.insert(uid(rng));
    input.insert(input.end(), uniq.begin(), uniq.end());
    shuffle(input.begin(), input.end(), rng);

    cout << "INSERT" << endl;

    start = clock();
    for (int x : input)
        st.insert(x);
    cout << "PBDS: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    for (int x : input)
        rbt.insert(x);
    cout << "Red Black: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;
}

void testFind() {
    uniform_int_distribution<int> uid(1, 1e9);
    vector<int> vals(input.begin(), input.end());
    vector<bool> ans1, ans2;
    for (int i=0; i<N; i+=2)
        vals[i] = uid(rng);
    shuffle(vals.begin(), vals.end(), rng);
    ans1.reserve(N);
    ans2.reserve(N);

    cout << "FIND" << endl;

    start = clock();
    for (int x : vals)
        ans1.push_back(st.find(x) != st.end());
    cout << "PBDS: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    for (int x : vals)
        ans2.push_back(rbt.find(x) != rbt.tNil);
    cout << "Red Black: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    assert(ans1 == ans2);
}

void testRank() {
    vector<int> vals(input.begin(), input.end()), ans1, ans2;
    shuffle(vals.begin(), vals.end(), rng);
    ans1.reserve(N);
    ans2.reserve(N);

    cout << "RANK" << endl;

    start = clock();
    for (int x : vals)
        ans1.push_back(st.order_of_key(x));
    cout << "PBDS: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    for (int x : vals)
        ans2.push_back(rbt.osRank(rbt.find(x)));
    cout << "Red Black: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    // order_of_key returns strictly smaller instead of less than or equal, so I decrement 1 from ans2 to compensate
    for (int &x : ans2)
        x--;
    assert(ans1 == ans2);
}

void testKth() {
    uniform_int_distribution<int> uid(0, (int) st.size() - 1);
    vector<int> vals(N), vals2, ans1, ans2;
    for (int &x : vals)
        x = uid(rng);
    vals2 = vals;
    for (int &x : vals2)
        x++;    // increment 1 cause RBTree is one-indexed
    ans1.reserve(N);
    ans2.reserve(N);

    cout << "KTH" << endl;

    start = clock();
    for (int x : vals)
        ans1.push_back(*st.find_by_order(x));
    cout << "PBDS: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    for (int x : vals2)
        ans2.push_back(rbt.osSelect(rbt.getRoot(), x));
    cout << "Red Black: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    assert(ans1 == ans2);
}

void testErase() {
    cout << "ERASE" << endl;

    start = clock();
    for (int x : input)
        st.erase(x);
    cout << "PBDS: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    for (int x : input)
        rbt.erase(x);
    cout << "Red Black: " << (double) (clock() - start) / CLOCKS_PER_SEC << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    testInsert();
    testFind();
    testRank();
    testKth();
    testErase();

    return 0;
}