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


// Search tree

struct node_s {
    int elem;
    node_s *left;
    node_s *right;
    node_s (int k) {elem = k; left = right = 0;}
};

node_s *ins_st(node_s *t, int k) {
    if (t==NULL)
        return new node_s(k);
    if (k < t->elem)
        t->left = ins_st (t->left, k);
    else if (k < t->elem)
        t->right = ins_st (t->right, k);
    return t;
}

node_s *findmin_s (node_s *t) {
    return t->left ? findmin_s (t->left) : t;
}

node_s *removemin_s (node_s *t){
    if(t->left == NULL)
        return t->right;
    t->left = removemin_s (t->left);
    return t;
}

node_s *remove_s (node_s *t, int k) {
    if(t == NULL) return 0;
    if (k < t->elem)
        t->left = remove_s (t->left, k);
    else if (k > t->elem)
        t->right = remove_s (t->right, k);
    else //  k == t->elem
    {
        node_s *q = t->left;
        node_s *r = t->right;
        delete t;
        if (r == NULL) return q;
        node_s *min = findmin_s(r);
        min->right = removemin_s(r);
        min->left = q;
        return min;
    }
    return t;
}


// other


struct node {
    int elem;
    unsigned char height;
    char color;
    node* left = nullptr;
    node* right = nullptr;
    node* parent = nullptr;
    node(int k, char c) {elem = k; left = right = 0; height = 1; color = c;} // r - red; b - black
};

node *root(NULL);

unsigned char height(node *t) {
    return t ? t->height : 0;
}

int heightdif (node *t) {
    return height(t->right) - height(t->left);
}

void fixheight (node *t) {
    unsigned char hl = height(t->left);
    unsigned char hr = height(t->right);
    t->height = (hl > hr ? hl : hr) + (t->color == 'b' ? 1 : 0);
}

node *rotateright (node *t) {
    node *q = t->left;
    t->left = q->right;
    if (q->right != NULL) q->right->parent = t;
    if (q != NULL) q->parent = t->parent;
    if (t->parent) {
        if (t == t->parent->right)
            t->parent->right = q;
        else
            t->parent->left = q;
    }
    else {
        root = q;
    }
    q->right = t;
    if (t != NULL) t->parent = q;
    fixheight (t);
    fixheight (q);
    return q;
}

node *rotateleft (node *t) {
    node *q = t->right;
    t->right = q->left;
    if (q->left != NULL) q->left->parent = t;
    if (q != NULL) q->parent = t->parent;
    if (t->parent) {
        if (t == t->parent->left)
            t->parent->left = q;
        else
            t->parent->right = q;
    }
    else {
        root = q;
    }
    q->left = t;
    if (t != NULL) t->parent = q;
    fixheight (t);
    fixheight (q);
    return q;
}


// AVL tree



node *balance (node *t) {
    fixheight(t);
    if(heightdif(t) == 2)
    {
        if(heightdif(t->right) < 0)
            t->right = rotateright(t->right);
        return rotateleft(t);
    }
    if(heightdif(t)==-2)
    {
        if(heightdif(t->left) > 0)
            t->left = rotateleft(t->left);
        return rotateright(t);
    }
    return t;
}

node *ins_avl(node *t, int k) {
    if(!t) return new node(k, 'b');
    if (k < t->elem)
        t->left = ins_avl (t->left, k);
    else if (k > t->elem)
        t->right = ins_avl(t->right, k);
    return balance(t);
}

node *findmin (node *t) {
    return t->left ? findmin (t->left) : t;
}

node *removemin (node *t)
{
    if(t->left == NULL)
        return t->right;
    t->left = removemin (t->left);
    return balance (t);
}

node *remove(node *t, int k) {
    if(t == NULL) return 0;
    if (k < t->elem)
        t->left = remove (t->left, k);
    else if (k > t->elem)
        t->right = remove (t->right, k);
    else //  k == t->elem
    {
        node *q = t->left;
        node *r = t->right;
        delete t;
        if (r == NULL) return q;
        node *min = findmin(r);
        min->right = removemin(r);
        min->left = q;
        return balance (min);
    }
    return balance(t);
}


// red-black tree

void insreb(node *&x) {
    while (x != root && x->parent->color == 'r') {
        if (x->parent == x->parent->parent->left) {
            node *u = x->parent->parent->right;
            if (u != NULL && u->color == 'r') { // uncle is red
                x->parent->color = 'b';
                u->color = 'b';
                x->parent->parent->color = 'r';
                x = x->parent->parent;
            }
            else { // uncle is black
                if (x == x->parent->right) {
                    // rotate
                    x = x->parent;
                    x = rotateleft(x);////////////////
                }
                // recolor and rotate
                x->parent->color = 'b';
                x->parent->parent->color = 'r';
                x->parent->parent = rotateright(x->parent->parent);
            }
        }
        else {
            // mirror
            node *u = x->parent->parent->left;
            if (u != NULL && u->color == 'r') {
                x->parent->color = 'b';
                u->color = 'b';
                x->parent->parent->color = 'r';
                x = x->parent->parent;
            }
            else {
                if (x == x->parent->left) {
                    x = x->parent;
                    x = rotateright(x);///////////////
                }
                x->parent->color = 'b';
                x->parent->parent->color = 'r';
                x->parent->parent = rotateleft(x->parent->parent);
            }
        }
    }
    root->color = 'b';
}

node *ins_rb(node *&T, int k) {
    if (T == NULL) {
        T = new node (k,'b');
        root = T;
        return T;
    }
    node *t(T);
    while (!((k > t->elem && t->right == NULL) || (k < t->elem && t->left == NULL))) {
        if (k < t->elem)
            t = t->left;
        else if (k > t->elem)
            t = t->right;
        else break;
    }
    if (k < t->elem) {
        t->left = new node (k,'r');
        t->left->parent = t;
        insreb (t->left);
    }
    else if (k > t->elem) {
        t->right = new node (k,'r');
        t->right->parent = t;
        insreb (t->right);
    }
    return root;
}


int main(){
    node *T(NULL);
    T = ins_rb (T,10);
    T = ins_rb (T,32);
    T = ins_rb (T,15);
    //T = ins_rb (T,24);
    //T = ins_rb (T,1);
    cout << T->elem;
    //cout << T->color;
}