public class ArrayDeque<T> {
    int initial_size = 8;
    int list_size;
    int front_pos, end_pos;
    T[] list;

    public ArrayDeque(){
        list = (T[]) new Object[initial_size];
        list_size = 0;
        front_pos = 0;
        end_pos = 1;
    }

    public T[] resize(){
        T[] temp = list;
        list = (T[]) new Object[list_size * 2];
//        System.arraycopy(temp, 0, list, 0, temp.length);
        for (int i = 0; i < list_size; i++){
            list[i] = temp[(front_pos + i + 1) % list_size];
        }
        front_pos = list.length - 1;
        end_pos = list_size;
        return list;
    }

    public void addFirst(T item){
        if (list_size == list.length){
            resize();
        }
        list[front_pos] = item;
        front_pos--;
        if (front_pos < 0){
            front_pos = list.length - 1;
        }
        list_size++;
    }

    public void addLast(T item){
        if (list_size == list.length){
            resize();
        }
        list[end_pos] = item;
        end_pos = (end_pos + 1) % list.length;
        list_size += 1;
        return;
    }


    public void printDeque(){
        for (int i = 0; i < list_size; i++){
            int p = (i + front_pos + 1) % list.length;
            System.out.printf("%s ", list[p]);
        }
        System.out.println();
    }

    public T removeFirst(){
        int ret_pos = (front_pos + 1) % list_size;
        T ret = list[ret_pos];
        list[ret_pos] = null;
        front_pos = ret_pos;
        list_size -= 1;
        return ret;
    }


    public T removeLast(){
        int ret_pos = (end_pos - 1 + list.length) % list.length;
        T ret = list[ret_pos];
        list[ret_pos] = null;
        end_pos = ret_pos;
        list_size -= 1;
        return ret;
    }

    public void p(){
        for (int i = 0; i < list.length; i++){
            System.out.printf("%s ", list[i]);
        }
        System.out.println();
    }

    public static void main(String[] args){
        ArrayDeque<Integer> a = new ArrayDeque<>();
        for (Integer i = 0; i < 9; i++){
            a.addFirst(i);
            a.addLast(i + 100);
            a.printDeque();
            // System.out.println(a.list_size);
        }
        for (Integer i = 0; i < 9; i++) {
            a.addLast(i + 100);
            a.printDeque();
            System.out.println(a.list_size);
        }

    }
}