import java.util.*;
import java.lang.*;
import java.io.*;

class Test
{
   static class Node<T>
   {
      Node<T> left, right;
      T data;
      int subtreeCount;
      Node(T data) { this.data = data; subtreeCount = 1; }
      
      public String toString(int spaces, char leftRight)
      {
         return String.format("%" + spaces + "s%c: %s\n", "", leftRight, data.toString())
                 + (left != null ? left.toString(spaces+3, 'L') : "")
                 + (right != null ? right.toString(spaces+3, 'R') : "");
      }
      
      int subtreeSize(Node<T> node)
      {
         if (node == null)
            return 0;
         return node.subtreeCount;
      }
      
      // combined add and get into 1 function for simplicity
      // if data is null, it is an get, otherwise it's an add
      private T addGet(int index, T data)
      {
         if (data != null)
            subtreeCount++;
         if (index == subtreeSize(left) && data == null)
            return this.data;
         if (index <= subtreeSize(left))
         {
            if (left == null && data != null)
               return (left = new Node<>(data)).data;
            else
               return left.addGet(index, data);
         }
         else if (right == null && data != null)
            return (right = new Node<>(data)).data;
         else
            return right.addGet(index-subtreeSize(left)-1, data);
      }
   }
   
   static class TreeArray<T>
   {
      private Node<T> root;
      public int size() { return (root == null ? 0 : root.subtreeCount); }
      
      void add(int index, T data)
      {
         if (index < 0 || index > size())
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
         if (root == null)
            root = new Node<>(data);
         else
            root.addGet(index, data);
      }
      
      T get(int index)
      {
         if (index < 0 || index >= size())
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
         return root.addGet(index, null);
      }

      @Override
      public String toString() { return root == null ? "Empty" : root.toString(1, 'X'); }
   }

   public static void main(String[] args)
   {
      TreeArray<String> tree = new TreeArray<>();
      tree.add(0, "a");
      tree.add(0, "b");
      tree.add(1, "c");
      tree.add(2, "d");
      tree.add(1, "e");
      tree.add(0, "f");
      tree.add(6, "g");
      tree.add(7, "h");
      System.out.println("Tree view:");
      System.out.print(tree);
      System.out.println("Elements in order:");
      for (int i = 0; i < tree.size(); i++)
         System.out.println(i + ": " + tree.get(i));
   }
}