using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        var solution = new Solution();

        solution.AddNum(1);

        solution.AddNum(3);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

        solution.AddNum(2);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

        solution.AddNum(7);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

        solution.AddNum(5);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

        solution.AddNum(6);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

        solution.AddNum(4);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

        solution.AddNum(4);

        Console.WriteLine(string.Join(",", solution.GetIntervals()));

    }

}

​

public class Solution

{

    private BST _tree;

    public Solution()

    {

        _tree = new BST();

    }

    public void AddNum(int val) 

    {

        var node = _tree.Find(val);

        if (node != null)

            return;

        var left = _tree.FindPrev(val);

        var right = _tree.FindNext(val);

        if (left != null && right != null && left.val.end == val -1 && right.val.start == val + 1)

        {

            left.val.end = right.val.end;

            _tree.Del(right.key);

        }

        else if (left != null && left.val.end + 1 >= val)

        {

            left.val.end = Math.Max(val, left.val.end);

        }

        else if (right != null && right.val.start - 1 == val)

        {

            _tree.Del(right.key);

            _tree.Add(val, new Interval(val, right.val.end));

        }

        else

            _tree.Add(val, new Interval(val, val));

    }

    public List<Interval> GetIntervals() 

    {

        return _tree.Values();

    }

}

​

​

public class Node

{

    public Node left;

    public Node right;

    public int  key;

    public Interval val;

    public Node(int key, Interval val)

    {

        this.key = key;

        this.val = val;

    }

}

​

public class Interval

{

    public int start;

    public int end;

    public Interval(int s, int e)

    {

        this.start = s;

        this.end = e;

    }

    public override string ToString()

    {

        return string.Format("[{0}, {1}] ", start, end);

    }

}

​

public class BST

{

    private Node _root;

    public BST()

    {

        _root = null;

    }

    public List<Interval> Values()

    {

        var ans = new List<Interval>();

        var stack = new Stack<Node>();

        var node = _root;

        while (stack.Count > 0 || node != null)

        {

            while (node != null)

            {

                stack.Push(node);

                node = node.left;

            }

            node = stack.Pop();

            ans.Add(node.val);

            node = node.right;

        }

        return ans;

    }

    // log(n)

    public void Add(int key, Interval val)

    {

        _root = Add(_root, key, val);

    }

    private Node Add(Node node, int key, Interval val)

    {

        if (node == null)

            return new Node(key, val);

        if (node.key == key)

            node.val = val;

        else if (node.key < key)

            node.right = Add(node.right, key, val);

        else

            node.left = Add(node.left, key, val);

        return node;

    }

    // log(n)

    public Node FindPrev(int key)

    {

        return FindPrev(_root, key);

    }

    private Node FindPrev(Node node, int key)

    {

        if (node == null)

            return null;

        if (node.key >= key)

            return FindPrev(node.left, key);

        else

            return FindPrev(node.right, key) ?? node;

    }

    // log(n)

    public Node FindNext(int key)

    {

        return FindNext(_root, key);

    }

    private Node FindNext(Node node, int key)

    {

        if (node == null)

            return null;

        if (node.key <= key)

            return FindNext(node.right, key);

        else

            return FindNext(node.left, key) ?? node;

    }

    // log(n)

    public Node Find(int key)

    {

        var node = _root;

        while (node != null)

        {

            if (node.key == key)

                return node;

            else if (node.key > key)

                node = node.left;

            else

                node = node.right;

        }

        return node;

    }

    public void Del(int key)

    {

        _root = Del(_root, key);

    }

    private Node Del(Node node, int key)

    {

        if (node == null)

            return null;

        if (node.key < key)

            node.right = Del(node.right, key);

        else if (node.key > key)

            node.left = Del(node.left, key);

        else

        {

            if (node.left == null)

                return node.right;

            else if (node.right == null)

                return node.left;

            var min = DelMin(node.right);

            min.left = node.left;

            min.right = node.right;

            node = min;

        }

        return node;

    }

    private Node DelMin(Node node)

    {

        var parent = node;

        while (node.left != null)

        {

            parent = node;

            node = node.left;

        }

        parent.left = node.right;

        return node;

    }

}