import java.util.*;


public class MinHeap
{
int[] nulldata = {0, 0};
//   public MinHeap()
//   {
//      data = new ArrayList<int[]>();
//      data.add(null);
//   }

   public MinHeap(int[] newconstruction)
   {
	   data = new ArrayList<int[]>();
	   data.add(nulldata);
	   data.add(newconstruction);
	   //System.out.println(data.size());
   }


   public void add(int[] newdata)
   {
      // Add a new leaf
      data.add(null);
      int index = data.size()-1;

      // Demote parents that are larger than the new element
      while (index > 1
            && getParent(index) > (newdata[0]))
      {
         data.set(index, getParentdeep(index));
         index = getParentIndex(index);
      }

      // Store the new element into the vacant slot
      data.set(index, newdata.clone());
   }


   public int[] peek()
   {
      return data.get(1);
   }


   public int[] remove()
   {
      int[] minimum;

//      for (int k = 0; k < data.get(0).length; k++){
//
//			System.out.printf("%d, ", data.get(0)[k]);
//
//		}
//		System.out.println("");

//	      for (int k = 0; k < data.get(1).length; k++){
//
//				System.out.printf("%d, ", data.get(1)[k]);
//
//			}
//			System.out.println("");

//      System.out.println(data.get(1)[data.get(1).length-1]);
//      System.out.println(data.size());

      minimum = data.get(1);

      // Remove last element
      int lastIndex = data.size() - 1;
      int[] last = data.remove(lastIndex);

      if (lastIndex > 1)
      {
         data.set(1, last);
         fixHeap();
      }

      return minimum;
   }


   private void fixHeap()
   {
      int[] root = data.get(1);

      int lastIndex = data.size() - 1;
      // Promote children of removed root while they are larger than last

      int index = 1;
      boolean more = true;
      while (more)
      {
         int childIndex = getLeftChildIndex(index);
         if (childIndex <= lastIndex)
         {
            // Get smaller child

            // Get left child first
            int[] child = getLeftChilddeep(index);

            // Use right child instead if it is smaller
            if (getRightChildIndex(index) <= lastIndex
                  && getRightChilddeep(index)[0] < child[0])
            {
               childIndex = getRightChildIndex(index);
               child = getRightChilddeep(index);
            }

            // Check if larger child is smaller than root
            if (child[0] < root[0])
            {
               // Promote child
               data.set(index, child);
               index = childIndex;
            }
            else
            {
               // Root is smaller than both children
               more = false;
            }
         }
         else
         {
            // No children
            more = false;
         }
      }

      // Store root element in vacant slot
      data.set(index, root);
   }


   public int size()
   {
      return data.size() -1;
   }


   private static int getLeftChildIndex(int index)
   {
      return 2 * index;
   }


   private static int getRightChildIndex(int index)
   {
      return 2 * index + 1;
   }


   private static int getParentIndex(int index)
   {
      return index / 2;
   }


//   private int getLeftChild(int index)
//   {
//      return data.get(2 * index)[1];
//   }
//
//
//   private int getRightChild(int index)
//   {
//      return data.get(2 * index + 1)[1];
//   }

   private int getParent(int index)
   {
      return data.get(index / 2)[0];
   }

   private int[] getLeftChilddeep(int index)
   {
      return data.get(2 * index).clone();
   }


   private int[] getRightChilddeep(int index)
   {
      return data.get(2 * index + 1).clone();
   }

   private int[] getParentdeep(int index)
   {
      return data.get(index / 2).clone();
   }

   private ArrayList<int[]> data;
}