#include<bits/stdc++.h>
using namespace std;
#define DEQUE_SIZE 100005
template<typename T>
struct Node_deque{
    T value;
    Node_deque* last,*next;
    Node_deque(const T& _value){
        value=_value;
        last=nullptr;
        next=nullptr;
    }
};
template<typename T>
struct my_deque{
    int deque_size;
    Node_deque<T>* start,*target;
    
    my_deque(){
        target=nullptr;
        start=nullptr;
        deque_size=0;
    }
    ~my_deque(){
        clear();
    }
    void clear(){
        while(!empty()){
            pop_front();
        }
    }
    int size(){
        return deque_size;
    }
    bool empty(){
        return deque_size==0;
    }
    T front(){
        if(empty()) return T();
        return start->value;
    }
    T back(){
        if(empty()) return T();
        return target->value;
    }
    bool push_front(const T& value){
    	if(deque_size+1>DEQUE_SIZE) return false;
        Node_deque<T>* new_node=new Node_deque<T>(value);
        if(deque_size==0){
            start=target=new_node;
            deque_size++;
            return 1;
        }
        new_node->next=start;
        start->last=new_node;
        start=new_node;
        deque_size++;
        return 1;
    }
    bool push_back(const T& value){
    	if(deque_size+1>DEQUE_SIZE) return false;
        Node_deque<T>* new_node=new Node_deque<T>(value);
        if(deque_size==0){
            start=target=new_node;
            deque_size++;
            return 1;
        }
        new_node->last=target;
        target->next=new_node;
        target=new_node;
        deque_size++;
        return 1;
    }
    bool pop_front(){
        if(deque_size==0) return false;
        Node_deque<T>* t=start;
        if(deque_size==1){
            start=target=nullptr;
            delete t;
            deque_size--;
            return true;
        }
        start=start->next;
        start->last=nullptr;
        delete t;
        deque_size--;
        return true;
    }
    bool pop_back(){
        if(deque_size==0) return false;
        Node_deque<T>* t=target;
        if(deque_size==1){
            start=target=nullptr;
            delete t;
            deque_size--;
            return true;
        }
        target=target->last;
        target->next=nullptr;
        delete t;
        deque_size--;
        return true;
    }
};