import java.util.*;

public class Main {

    static int rotations = 0;

    static class Node {
        int key;
        Node left;
        Node right;
        int height;

        Node(int key) {
            this.key = key;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }

    // Create a new node
    public static Node createNode(int key) {
        return new Node(key);
    }

    // Return stored height
    public static int height(Node node) {
        if (node == null)
            return 0;

        return node.height;
    }

    // Calculate balance factor
    public static int getBalance(Node node) {
        if (node == null)
            return 0;

        return height(node.left) - height(node.right);
    }

    // Right Rotation
    public static Node rightRotate(Node y) {

        rotations++;

        Node x = y.left;
        Node T2 = x.right;

        // Rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = 1 + Math.max(
            height(y.left),
            height(y.right)
        );

        x.height = 1 + Math.max(
            height(x.left),
            height(x.right)
        );

        return x;
    }

    // Left Rotation
    public static Node leftRotate(Node x) {

        rotations++;

        Node y = x.right;
        Node T2 = y.left;

        // Rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = 1 + Math.max(
            height(x.left),
            height(x.right)
        );

        y.height = 1 + Math.max(
            height(y.left),
            height(y.right)
        );

        return y;
    }

    // AVL Insertion
    public static Node insert(Node node, int key) {

        // 1. Normal BST insertion
        if (node == null) {
            return createNode(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; // Duplicate keys
        }

        // 2. Update height
        node.height = 1 + Math.max(
            height(node.left),
            height(node.right)
        );

        // 3. Calculate balance factor
        int balance = getBalance(node);

        // 4. LL Case
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }

        // 5. RR Case
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }

        // 6. LR Case
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 7. RL Case
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // Tree is already balanced
        return node;
    }

    // Inorder traversal
    public static void inorder(Node root) {

        if (root == null)
            return;

        inorder(root.left);

        System.out.print(
            root.key + "(" + root.height + ") "
        );

        inorder(root.right);
    }

    public static void main(String[] args) {

        int[] arr = {
            50, 30, 70, 20, 40, 60, 80,
            10, 5, 15, 25, 27, 26, 65,
            62, 64, 90, 100, 95
        };

        Node root = null;

        for (int key : arr) {
            root = insert(root, key);
        }

        System.out.println("Inorder traversal:");
        inorder(root);

        System.out.println();

        System.out.println("Total rotations = " + rotations);

        System.out.println("Root = " + root.key);
    }
}