import java.util.*;

// Do not edit the class below except for the buildHeap,
// siftDown, siftUp, peek, remove, and insert methods.
// Feel free to add new properties and methods to the class.
class Program {
  static class MinHeap {
    List<Integer> heap = new ArrayList<Integer>();

    public MinHeap(List<Integer> array) {
      heap = buildHeap(array);
    }

    public List<Integer> buildHeap(List<Integer> array) {
      for (int i=array.size()-1; i>=0; i--){
                siftDown(i, array.size()-1, array);
            }
            return array;
    }

    public void siftDown(int currentIdx, int endIdx, List<Integer> heap) {
      // basically ok theres a hole at root, gotta fill with a child
            // then gotta fill that node's child with a child etc etc
            int temp;
            int leftChild;
            int rightChild;
            while (endIdx <= currentIdx){
                if ((heap.get(currentIdx) < heap.get(2 * currentIdx + 1)) && (heap.get(currentIdx) < heap.get(2 * currentIdx + 2))){
                    break;
                }
                if ((heap.get(2 * currentIdx + 1) <= endIdx)){
                    temp = heap.get(currentIdx);
                    leftChild = heap.get(2 * currentIdx + 1);
                    (heap.get(currentIdx)).set(leftChild);
                    heap.get(2 * currentIdx + 1) = temp;
                    currentIfx = heap.get(2 * currentIdx + 1);
                }
                if ((heap.get(2 * currentIdx + 1) <= endIdx) && (heap.get(2 * currentIdx + 2) <= endIdx)){
                    if (heap.get(2 * currentIdx + 1) < heap.get(2 * currentIdx + 2)) {
                        temp = heap.get(currentIdx);
                        heap.get(currentIdx) = heap.get(2 * currentIdx + 1);
                        heap.get(2 * currentIdx + 1) = temp;
                        currentIfx = heap.get(2 * currentIdx + 1);
                    }
                    else if (heap.get(2 * currentIfx + 2) < heap.get(2 * currentIdx + 1)){
                        temp = heap.get(currentIdx);
                        heap.get(currentIdx) = heap.get(2 * currentIdx + 2);
                        heap.get(2 * currentIdx + 2) = temp;
                        currentIfx = heap.get(2 * currentIdx + 2);
                    }
                }
            }
    }

    public void siftUp(int currentIdx, List<Integer> heap) {
            int siftValue = heap.get(heap.size() - 1);
            for (int currentIdx = heap.size() - 1; currentIdx > 0; currentIdx--) {
                if (siftValue < heap.get((currentIdx-1)/2)){
                    int tempValue = heap.get((currentIdx-1)/2);
                    heap.get((currentIdx-1)/2) = siftValue;
                    tempValue = heap.get(currentIdx);
                }
            }
    }

    public int peek() {
      if (heap.get(0) != null){
                return heap.get(0);
            }
      return -1;
    }

    public int remove() {
      // Swap last element with root, resize to destroy old root, sift down
            int tempValue;
            if (heap.size() == 1){
                tempValue = heap.get(0);
                heap.subList(0, heap.size()).clear();
                return tempValue;
            }
            if (heap.size() >= 2){
                tempValue = heap.get(0);
                heap.get(0) = heap.get(heap.size()-1);
                heap.get(heap.size()-1) = tempValue;
                heap.subList(heap.size() - 1, heap.size()).clear();
                siftDown(0, heap.size()-1, heap);
                return tempValue;
            }
      return -1;
    }

    public void insert(int value) {
            heap.add(value);
            siftUp(heap.size()-1, heap); // is this right?
        }
  }
}