import java.util.Arrays;
import java.util.NoSuchElementException;
 
/**
 * Deque (double-ended queue) implementation which uses an array to store
 * references to the objects added to the deque.
 */
class Deque<T> {
    private Object[] data = new Object[1];
    // index of the most lastly added object (-1 if no object has been added)
    private int lo = -1;
    // index of the most recently added object
    private int hi = -1;
 
    public void addFront(T value) {
        if (lo == -1) {
            data[0] = value;
            lo = 0;
            hi = 0;
        } else {
            changeArraySizeIfNeeded();
            lo = dec(lo);
            data[lo] = value;
        }
        System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("addFront(%s):", value), Arrays.toString(data), lo, hi);
    }
 
    public void addBack(T value) {
        if (hi == -1) {
            data[0] = value;
            lo = 0;
            hi = 0;
        } else {
            changeArraySizeIfNeeded();
            hi = inc(hi);
            data[hi] = value;
        }
        System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("addBack(%s):", value), Arrays.toString(data), lo, hi);
    }
 
    public T popFront() {
        if (lo == -1) {
            throw new NoSuchElementException("The deque is empty");
        }
 
        T value = (T) data[lo];
        data[lo] = null;
        if (lo == hi) {
            lo = -1;
            hi = -1;
        } else {
            lo = inc(lo);
        }
        changeArraySizeIfNeeded();
        System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("popFront() = %s:", value), Arrays.toString(data), lo, hi);
        return value;
    }
 
    public T popBack() {
        if (hi == -1) {
            throw new NoSuchElementException("The deque is empty");
        }
 
        T value = (T) data[hi];
        data[hi] = null;
        if (lo == hi) {
            lo = -1;
            hi = -1;
        } else {
            hi = dec(hi);
        }
        changeArraySizeIfNeeded();
        System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("popBack() = %s:", value), Arrays.toString(data), lo, hi);
        return value;
    }
 
    public T peekFront() {
        if (lo == -1) {
            throw new NoSuchElementException("The deque is empty");
        }
        return (T) data[lo];
    }
 
    public T peekBack() {
        if (hi == -1) {
            throw new NoSuchElementException("The deque is empty");
        }
        return (T) data[hi];
    }
 
    /**
     * Decrements the given index in a cyclic manner (modulo data.length)
     */
    private int dec(int i) {
        i--;
        if (i < 0) {
            i += data.length;
        }
        return i;
    }
 
    /**
     * Increments the given index in a cyclic manner (modulo data.length)
     */
    private int inc(int i) {
        return ++i % data.length;
    }
 
    /**
     * Doubles the size of the `data` array in case it is full and
     * decreases the size of `data` array twice if it is filled
     * at one quarter or less
     */
    private void changeArraySizeIfNeeded() {
        int pureDataLength = lo < 0 ?
                0 :
                moduloDistance(lo, hi, data.length);
 
        if (pureDataLength == data.length) {
            data = resizeArray(data, lo, hi, 2 * data.length);
            hi = pureDataLength - 1;
            lo = 0;
        } else if (pureDataLength != 0 && data.length / pureDataLength >= 4) {
            data = resizeArray(data, lo, hi, data.length / 2);
            hi = pureDataLength - 1;
            lo = 0;
        } else if (pureDataLength == 0) {
            data = new Object[1];
        }
    }
 
    /**
     * Computes the distance between `lo` and `hi` as if
     * they were put into a cyclic array of size `n`
     */
    private static int moduloDistance(int lo, int hi, int n) {
        assert lo >= 0 && hi >= 0;
 
        return lo <= hi ?
            hi - lo + 1 :
            n - lo + hi + 1;
    }
 
    /**
     * Copies the given array into a new one of the {@code newSize} size
     * @param src the source array
     * @param lo points to the first element in the sequence to be copied
     * @param hi points to the last element in the sequence to be copied.
     *           It is not necessary for `lo` to be less, than `hi`:
     *           this method copies the data from the `src` as if it would be cyclic
     * @param newSize size of the resulting array
     */
    private static Object[] resizeArray(Object[] src, int lo, int hi, int newSize) {
        assert newSize >= 0;
        assert moduloDistance(lo, hi, src.length) <= newSize;
 
        Object[] resizedArray = new Object[newSize];
        if (lo <= hi) {
            System.arraycopy(src, lo, resizedArray, 0, hi - lo + 1);
        } else {
            System.arraycopy(src, lo, resizedArray, 0, src.length - lo);
            System.arraycopy(src, 0, resizedArray, src.length - lo, hi + 1);
        }
        return resizedArray;
    }
 
    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<>();
        for (int i = 3; i >= 0; i--) {
            deque.addFront(i);
        }
        for (int i = 4; i <= 7; i++) {
            deque.addBack(i);
        }
        System.out.println();
        for (int i = 0; i < 4; i++) {
            deque.popFront();
            deque.popBack();
        }
        deque.addBack(1);
        deque.addFront(0);
    }
}