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

class RATreeNode
{
	int numBelow;
	RATreeNode left, right;
	int val;
	boolean v;

	public RATreeNode (int in)
	{
		numBelow = 1;
		left = null;
		right = null;
		val = in;
		v = false;
	}
	
	public boolean isLeaf ()
	{
		return left == null && right == null;
	}
	
	public void setChildren (RATreeNode newLeft, RATreeNode newRight)
	{
		left = newLeft;
		right = newRight;
	}

	public RATreeNode getLeft ()
	{
		return left;
	}

	public RATreeNode getRight ()
	{
		return right;
	}
	
	public void setNumBelow (int newNumBelow)
	{
		numBelow = newNumBelow;
	}

	public int getNumBelow ()
	{
		return numBelow;
	}

	public void setVal (int newVal)
	{
		val = newVal;
	}
	
	public int getVal ()
	{
		return val;
	}

	public int getVal (int index)
	{
		if (index >= numBelow)
			throw new IndexOutOfBoundsException();
		
		if (isLeaf())
			return val;

		balance();
		
		if (left.getNumBelow() > index)
			return left.getVal(index);
		return right.getVal(index - left.getNumBelow());
	}
	
	public void insert (RATreeNode node, int index)
	{
		if (index > numBelow)
			throw new IndexOutOfBoundsException();
		
		numBelow += node.getNumBelow();
		
		if (isLeaf())
		{
			if (index == 0)
			{
				left = node;
				right = new RATreeNode(val);
			}
			else
			{
				left = new RATreeNode(val);
				right = node;
			}
		}
		else
		{
			balance();

			if (index < left.getNumBelow())
				left.insert(node, index);
			else if (index > left.getNumBelow())
				right.insert(node, index - left.getNumBelow());
			else if (left.getNumBelow() < right.getNumBelow())
				left.insert(node, index);
			else
				right.insert(node, index - left.getNumBelow());
		}
	}
	
	public void insertSafe (RATreeNode node, int index)
	{
		if (index > numBelow)
			throw new IndexOutOfBoundsException();
		
		numBelow += node.getNumBelow();
		
		if (isLeaf())
		{
			if (index == 0)
			{
				left = node;
				right = new RATreeNode(val);
			}
			else
			{
				left = new RATreeNode(val);
				right = node;
			}
		}
		else
		{
			if (index < left.getNumBelow())
				left.insertSafe(node, index);
			else if (index > left.getNumBelow())
				right.insertSafe(node, index - left.getNumBelow());
			else if (left.getNumBelow() < right.getNumBelow())
				left.insertSafe(node, index);
			else
				right.insertSafe(node, index - left.getNumBelow());
		}
	}


	public int maxHeight ()
	{
		if (isLeaf())
			return 1;
		return 1 + Math.max(left.maxHeight(), right.maxHeight());
	}
	
	public void delete (int index)
	{
		if (index >= numBelow)
			throw new IndexOutOfBoundsException();

		numBelow--;
		
		if (index < left.getNumBelow() && left.isLeaf())
		{
			if (right.isLeaf())
				val = right.getVal(0);
			left = right.getLeft();
			right = right.getRight();
		}
		else if (index >= left.getNumBelow() && right.isLeaf())
		{
			if (left.isLeaf())
				val = left.getVal(0);
			right = left.getRight();
			left = left.getLeft();
		}
		else
		{
			balance();

			if (index < left.getNumBelow())
			{
				if (left.isLeaf())
				{
					numBelow++;
					delete(index);
				}
				else
					left.delete(index);
			}
			else
			{
				if (right.isLeaf())
				{
					numBelow++;
					delete(index);
				}
				else
					right.delete(index - left.getNumBelow());
			}
		}
	}
	
	public void balance ()
	{
		if (left.getNumBelow()/2 > right.getNumBelow())
		{
			int t = (left.getNumBelow() - right.getNumBelow()) / 2;
			RATreeNode best = null;
			for (RATreeNode i = left; !i.isLeaf(); i = i.getRight())
				if (best == null || 
				    Math.abs(t-i.getRight().getNumBelow()) < Math.abs(t-best.getRight().getNumBelow()))
					best = i;
			
			right.insert(best.getRight(), 0);
			for (RATreeNode i = left; i != best.getRight(); i = i.getRight())
				i.setNumBelow(i.getNumBelow() - best.getRight().getNumBelow());
			best.setNumBelow(best.getLeft().getNumBelow());
			best.setVal(best.getLeft().getVal());
			best.setChildren(best.getLeft().getLeft(), best.getLeft().getRight());
		}
		else if (right.getNumBelow()/2 > left.getNumBelow())
		{
			int t = (right.getNumBelow() - left.getNumBelow()) / 2;
			RATreeNode best = null;
			for (RATreeNode i = right; !i.isLeaf(); i = i.getLeft())
				if (best == null || 
				    Math.abs(t-i.getLeft().getNumBelow()) < Math.abs(t-best.getLeft().getNumBelow()))
					best = i;
			
			left.insert(best.getLeft(), 0);
			for (RATreeNode i = right; i != best.getLeft(); i = i.getLeft())
				i.setNumBelow(i.getNumBelow() - best.getLeft().getNumBelow());
			best.setNumBelow(best.getRight().getNumBelow());
			best.setVal(best.getRight().getVal());
			best.setChildren(best.getRight().getRight(), best.getRight().getLeft());
		}
	}
}

public class RATree
{
	private RATreeNode root = null;

	public RATree ()
	{
	}

	public void insert (int val, int index)
	{
		if (root == null)
		{
			if (index > 0)
				throw new IndexOutOfBoundsException();
			root = new RATreeNode(val);
		}
		else
		{
			root.insert(new RATreeNode(val), index);
		}
	}

	public int get (int index)
	{
		return root.getVal(index);
	}

	public int getSafe (int index)
	{
		return root.getVal(index);
	}

	public void delete (int index)
	{
		if (index == 0 && root.isLeaf())
			root = null;
		else
			root.delete(index);
	}

	public int maxHeight ()
	{
		if (root == null)
			return 0;
		return root.maxHeight();
	}

	public int size ()
	{
		if (root == null)
			return 0;
		return root.getNumBelow();
	}
}