public class Deque<T> {
    private Object[] deque;
    private int size;
    private int capacity;
    private int front;
    private int rear;

    public Deque() {
        capacity = 5;
        deque = new Object[capacity];
        size = 0;
        front = -1;
        rear = -1;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private void resize() {
        int newCapacity = capacity * 2;
        Object[] newDeque = new Object[newCapacity];
        int i = 0;
        int j = front;
        while (i < size) {
            newDeque[i] = deque[j];
            j = (j + 1) % capacity;
            i++;
        }
        deque = newDeque;
        capacity = newCapacity;
        front = 0;
        rear = size - 1;
    }

    public void addFirst(T element) {
        if (isFull()) {
            resize();
        }
        if (isEmpty()) {
            front = 0;
            rear = -1;
        } else {
            front = (front - 1 + capacity) % capacity;
        }
        deque[front] = element;
        size++;
    }

    public void addLast(T element) {
        if (isFull()) {
            resize();
        }
        if (isEmpty()) {
            front = 0;
            rear = -1;
        } else {
            rear = (rear + 1) % capacity;
        }
        deque[rear] = element;
        size++;
    }

    public T removeFirst() {
        if (isEmpty()) {
            return null;
        }
        T element = (T) deque[front];
        deque[front] = null;
        size--;
        if (isEmpty()) {
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        return element;
    }

    public T removeLast() {
        if (isEmpty()) {
            return null;
        }
        T element = (T) deque[rear];
        deque[rear] = null;
        size--;
        if (isEmpty()) {
            front = -1;
            rear = -1 ;
        } else {
            rear = (rear - 1 + capacity) % capacity;
        }
        return element;
    }

    public T peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return (T) deque[front];
    }

    public T peekLast() {
        if (isEmpty()) {
            return null;
        }
        return (T) deque[rear];
    }

    public int size() {
        return size;
    }
}