#include <iostream>

using namespace std;

struct node
{
    int data{};
    node* left = nullptr;
    node* right = nullptr;
    node* parent = nullptr;
    string color;
    int Rank;
};
class RB_TREE
{

    node* root;

public:
    RB_TREE() : root(nullptr) {}

    node* GetRoot()
    {
        return root;
    }

    void InsertNode(int stuff)
    {
        if(root == nullptr)
        {
            root = new node();
            root->data = stuff;
            root->parent = nullptr;
            root->color = "BLACk";
            //root->Rank = 1;
            cout << "Element inserted.\n";
        }
        else
        {
            node *Root = GetRoot();
            node* newnode = new node();
            newnode->data = stuff;

            while(Root != nullptr)
            {
                if(Root->data > stuff)
                {
                    if(Root->left == nullptr)
                    {
                        Root->left = newnode;
                        newnode->color = "RED";
                        newnode->parent = Root;
//                           newnode->Rank = 1;
//                           node* temp = newnode->parent;
//                           while(temp != nullptr)
//                           {
//                               temp->Rank ++;
//                               temp = temp->parent;
//                           }
                        cout << "Element inserted.\n";
                        break;
                    }
                    else
                    {
                        Root = Root->left;
                    }
                }
                else
                {
                    if(Root->right == nullptr)
                    {
                        Root->right = newnode;
                        newnode->color = "RED";
                        newnode->parent = Root;
//                           newnode->Rank = 1;
//                           node* temp = newnode->parent;
//                           while(temp != nullptr)
//                           {
//                               temp->Rank ++;
//                               temp = temp->parent;
//                           }
                           cout << "Element inserted.\n";
                           break;
                    }
                    else
                    {
                        Root = Root->right;
                    }
                }
            }
            RB_Insert_Fixup(newnode);

        }
    }


    void RB_Insert_Fixup(node* z)
    {
        while(z->parent->color == "RED")
        {
            node* grandparent = z->parent->parent;
            node* uncle = GetRoot();
            if(z->parent == grandparent->left)
            {
                if(grandparent->right)
                {
                    uncle = grandparent->right;
                }
                if(uncle->color == "RED")
                {
                    z->parent->color = "BLACK";
                    uncle->color = "BLACK";
                    grandparent->color = "RED";
                    if(grandparent->data != root->data)
                    {
                        z = grandparent;
                    }
                    else
                    {
                        break;
                    }
                }
                else if(z == grandparent->left->right)
                {
                    LeftRotate(z->parent);
                }
                else
                {
                    z->parent->color = "BLACK";
                    grandparent->color = "RED";
                    RightRotate(grandparent);
                    if(grandparent->data != root->data)
                    {
                        z = grandparent;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            else
            {
                if(grandparent->left)
                {
                    uncle = grandparent->left;
                }
                if(uncle->color == "RED")
                {
                    z->parent->color = "BLACK";
                    uncle->color = "BLACK";
                    grandparent->color = "RED";
                    if(grandparent->data != root->data)
                    {
                        z = grandparent;
                    }
                    else
                    {
                        break;
                    }
                }
                else if(z == grandparent->right->left)
                {
                    RightRotate(z->parent);
                }
                else
                {
                    z->parent->color = "BLACK";
                    grandparent->color = "RED";
                    LeftRotate(grandparent);
                    if(grandparent->data != root->data)
                    {
                        z = grandparent;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        root->color = "BLACK";
    }
    node* TreeSearch(int stuff)
    {
        node* temp = GetRoot();
        if(temp == nullptr)
        {
            return nullptr;
        }

        while(temp)
        {
            if(stuff == temp->data)
            {
                return temp;
            }
            else if(stuff < temp->data)
            {
                temp = temp->left;
            }
            else
            {
                temp = temp->right;
            }
        }
        return nullptr;
    }

    void LeftRotate(node* x)
    {
        node* nw_node = new node();
        if(x->right->left)
        {
            nw_node->right = x->right->left;
        }
        nw_node->left = x->left;
        nw_node->data = x->data;
        nw_node->color = x->color;
        x->data = x->right->data;

        x->left = nw_node;
        if(nw_node->left)
        {
            nw_node->left->parent = nw_node;
        }
        if(nw_node->right)
        {
            nw_node->right->parent = nw_node;
        }
        nw_node->parent = x;

        if(x->right->right)
        {
            x->right = x->right->right;
        }
        else
        {
            x->right = nullptr;
        }

        if(x->right)
        {
            x->right->parent = x;
        }
    }

    void RightRotate(node* x)
    {
        node* nw_node = new node();
        if(x->left->right)
        {
            nw_node->left = x->left->right;
        }
        nw_node->right = x->right;
        nw_node->data = x->data;
        nw_node->color = x->color;

        x->data = x->left->data;
        x->color = x->left->color;

        x->right = nw_node;
        if(nw_node->left)
        {
            nw_node->left->parent = nw_node;
        }
        if(nw_node->right)
        {
            nw_node->right->parent = nw_node;
        }
        nw_node->parent = x;

        if(x->left->left)
        {
            x->left = x->left->left;
        }
        else
        {
            x->left = nullptr;
        }

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

    void ReRank(node* temp)
    {
        if(!temp)
        {
            return;
        }

        ReRank(temp->left);

        ReRank(temp->right);

        if(temp->left == NULL && temp->right == NULL)
            temp->Rank = 1;
        else if (temp->left == NULL)
            temp->Rank = temp->right->Rank + 1;
        else if(temp->right == NULL)
            temp->Rank = temp->left->Rank + 1;
        else
            temp->Rank = temp->left->Rank + temp->right->Rank + 1;

    }
    int Select(node* temp,int i)
    {

        if(i==temp->Rank)
            return temp->data;
        if(i< temp->Rank)
            Select(temp->left,i);
        else if(i> temp->Rank)
        {
            i = i - temp->Rank;
            Select(temp->right,i);
        }

    }
//     void ReRank(node* p)
//     {
//         if(!p)
//            return
//
//        int sl=0 ,sr=0;
//        if(p->left)
//          sl=ReRank(p->left);
//        if(p->right)
//           sr=ReRank(p->right)
//     }
    void InorderTraversal(node* temp)
    {


        if(!temp)
        {
            return;
        }


        InorderTraversal(temp->left);
        cout << "--> " << temp->data << "<" << temp->color << ">" << "< " << temp->Rank << " >"<<endl;
        InorderTraversal(temp->right);
    }
};
int main()
{
    RB_TREE demo;
    int input,k;
    cin>>k;
while(true){
        switch(k)
        {

        case 1:
            cout<<"Enter The Number To Insert"<<endl;
            cin>>input;
            demo.InsertNode(input);
            cout<<endl;
        break;
        case 2:
            demo.ReRank(demo.GetRoot());
            demo.InorderTraversal(demo.GetRoot());
            cout<<demo.Select(demo.GetRoot(),1);
            cout<<endl;
        break;
        }
        //cout<<"Review The Tree"<<endl;

}
    return 0;
    }