public class AVLNode
{
    public int Key;
    public AVLNode Left, Right;
    public int Height;

    public AVLNode(int key)
    {
        Key = key;
        Height = 1;
    }
}

public class AVLTree
{
    private AVLNode root;

    int Height(AVLNode node) => node?.Height ?? 0;

    int BalanceFactor(AVLNode node) => Height(node.Left) - Height(node.Right);

    AVLNode RightRotate(AVLNode y)
    {
        var x = y.Left;
        var T2 = x.Right;

        x.Right = y;
        y.Left = T2;

        y.Height = Math.Max(Height(y.Left), Height(y.Right)) + 1;
        x.Height = Math.Max(Height(x.Left), Height(x.Right)) + 1;

        return x;
    }

    AVLNode LeftRotate(AVLNode x)
    {
        var y = x.Right;
        var T2 = y.Left;

        y.Left = x;
        x.Right = T2;

        x.Height = Math.Max(Height(x.Left), Height(x.Right)) + 1;
        y.Height = Math.Max(Height(y.Left), Height(y.Right)) + 1;

        return y;
    }

    public AVLNode Insert(AVLNode node, int key)
    {
        if (node == null)
            return new AVLNode(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 + Math.Max(Height(node.Left), Height(node.Right));

        int balance = BalanceFactor(node);

        if (balance > 1 && key < node.Left.Key)
            return RightRotate(node);

        if (balance < -1 && key > node.Right.Key)
            return LeftRotate(node);

        if (balance > 1 && key > node.Left.Key)
        {
            node.Left = LeftRotate(node.Left);
            return RightRotate(node);
        }

        if (balance < -1 && key < node.Right.Key)
        {
            node.Right = RightRotate(node.Right);
            return LeftRotate(node);
        }

        return node;
    }
}