#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
struct node{
    int key;
    struct node *left;
    struct node *right;
    int height;
};
int max(int a, int b)
{
    return (a>b)?a:b;
}
int height(struct node *n)
{
    if(n==NULL)
        return 0;
    return n->height;    
}
struct node *newnode(int key)
{
    struct node *node=(struct node*)malloc(sizeof(struct node));
    node->key=key;
    node->left=NULL;
    node->right=NULL;
    node->height=1;
    return (node);
}
struct node *rr(struct node *y)
{
    struct node *x=y->left;
    struct node *t2=x->right;
    x->right=y;
    y->left =t2;
    y->height=max(height(y->left),height(y->right)+1);
    x->height=max(height(x->left),height(x->right)+1);
    return x;
}
struct node *lr(struct node *x)
{
    struct node *y=x->left;
    struct node *t2=y->right;
    
    y->left =x;
    x->right=t2;
    x->height=max(height(x->left),height(x->right)+1);
    y->height=max(height(y->left),height(y->right)+1);
    return x;
}
int getb(struct node *n)
{
    if (n==NULL)
    {
        return 0;
    }
    return height(n->left) - height(n->right);
}
struct node * insert(struct node *node,int key)
{
    if(node==NULL)
        return(newnode(key));
    if(key<node->key)
        node->left =insert(node->left,key);
    else if(key > node-> key)
        node->right =insert(node->right,key);
    else
        return node;
        
    node->height=1+max(height(node->left),height(node->right));
    int bal=getb(node);
    if(bal>1 && key <node->left->key)
        return rr(node);
    if(bal<-1 && key>node->right->key)
        return lr(node);
    if(bal >1 && key> node->right->key)
        node->left=in(node->left);
        return rr(node);
    if(bal<-1 && key<node->right->k)
}