import java.util.*;

//import resources.*;

// NEUSTE : 15.11.18 , 20:37
public class Delivery {


    class MaxHeap extends Heap {
        MaxHeap(int[] elements) {
            super(elements);
        }

        @Override
        public int remove(){
            //TODO implement here. Removes the top element, restores heap and returns the removed element.
           swap(0 , end);
           int tmp = this.elements[end];
            --end;
            heap();

            return tmp;
        }

        @Override
        public void add(int ele){
            //TODO implement here
            if (end == this.elements.length-1){
                int [] tmp = new int[elements.length+1];
                for(int i = 0 ; i< elements.length;i++)
                {
                    tmp[i] = elements[i];

                }
                tmp[tmp.length-1] = ele;
                elements = tmp;
                end++;

            } else if(end < this.elements.length-1){

                this.elements[end++] = ele;
            }
            heap();
        }



        @Override
        protected void heap(){
            //TODO implement here and LEAVE the saveStep() at the end!!
            int startIndex = ((end) / 2); //Start Indes, erstes Parent mit Child

            //Schleife durchlauft von rechts nach links das array unt ruft uebrladene meth auf mit pos des curentParent
            for(int i = startIndex; i >= 0; --i) {
                heap(i);
            }

            saveStep();

        }
        public boolean doIExist(int pos)
        {
            return pos<=end;
        }
        boolean compareElements(int l , int r)
        {
            return elements[l] > elements[r];
        }

        protected void heap(int curParent){

            int curLeftChild = (2 * curParent) + 1;
            int curRightChild = (2 * curParent) + 2;
            int largestChild = curParent;

            if( doIExist(curLeftChild)&& compareElements(curLeftChild,curParent) )
            {
                largestChild = curLeftChild;
            }

            if( doIExist(curRightChild) && compareElements(curRightChild,curLeftChild) )
            {
                if(compareElements(curRightChild,curParent))
                {
                    largestChild = curRightChild;
                }

            }
            if( largestChild != curParent )
            {
                swap(curParent,largestChild);
                heap(largestChild);
            }

        }
        //Swap fuer zwei Elemente in einem Array
        public void swap(int x, int y){
            int tmp = this.elements[x];
            this.elements[x] = this.elements[y];
            this.elements[y] = tmp;

        }

        @Override
        public int[] sort(){
            //TODO implement here. Sort heap in-place using the given methods and return the sorted sequence.

                while ( end >1){
                    remove();
                   // heap();
                }
                if(end == 1)
                {
                    swap(0,1);
                }


            return this.elements;
        }

    }

    public Heap getMaxHeap(int[] sequence){
        return new MaxHeap(sequence);
    }

    class MinHeap extends Heap {
        MinHeap(int[] elements) {
            super(elements);
        }

        @Override
        public int remove(){
            //TODO implement here. Removes the top element, restores heap and returns the removed element.
            swap(0 , end);
           // System.out.println("pre : "+end);
            int tmp = this.elements[end];
            --end;
           // System.out.println("post : "+end);
            heap();


            return tmp;
        }

        @Override
        public void add(int ele){
            //TODO implement here
            if (end == this.elements.length-1){
                int [] tmp = new int[elements.length+1];
                for(int i = 0 ; i< elements.length;i++)
                {
                    tmp[i] = elements[i];

                }
                tmp[tmp.length-1] = ele;
                elements = tmp;
                end++;

            } else if(end < this.elements.length-1){

                this.elements[end++] = ele;
            }
            heap();
        }

        @Override
        protected void heap(){
            //TODO implement here and LEAVE the saveStep() at the end!!
            int startIndex = ((this.elements.length - 1) / 2);


            for(int i = startIndex; i >= 0; --i) {
                heap(i);
            }
            saveStep();
        }
        public boolean doIExist(int pos)
        {
            return pos<=end;
        }
        boolean compareElements(int l , int r)
        {
            return elements[l] > elements[r];
        }

        protected void heap(int curParent){

            int curLeftChild = (2 * curParent) + 1;
            int curRightChild = (2 * curParent) + 2;
            int largestChild = curParent;

            if( doIExist(curLeftChild)&& compareElements(curParent,curLeftChild) )
            {
                largestChild = curLeftChild;
            }

            if( doIExist(curRightChild) && compareElements(curLeftChild,curRightChild) )
            {
                if(compareElements(curParent,curRightChild))
                {
                    largestChild = curRightChild;
                }

            }
            if( largestChild != curParent )
            {
                swap(curParent,largestChild);
                heap(largestChild);
            }

        }
        //Swap fuer zwei Elemente in einem Array
        public void swap(int x, int y){
            int tmp = this.elements[x];
            this.elements[x] = this.elements[y];
            this.elements[y] = tmp;

        }

        @Override
        public int[] sort(){
            //TODO implement here. Sort heap in-place using the given methods and return the sorted sequence.
            int s = end;
            while ( end >1){
                remove();
                //heap();
            }
            if(end == 1)
            {
                swap(0,1);
            }
            for(int i = 1 ; i<=(elements.length)/2 ; i++)
            {
                swap(i-1,elements.length-i);
            }

            return this.elements;
        }

    }

    public Heap getMinHeap(int[] sequence){
        return new MinHeap(sequence);
    }



}