#include<bits/stdc++.h>
using namespace std;
#define LIST_SIZE 1005
template<typename T>
struct default_list{
	bool operator()(const T& a,const T& b) const{
		return false;
	}
};
template<typename T>
struct Node_list{
	T value;
    Node_list *last,*next;
    Node_list(const T& _value){
        value=_value;
        last=nullptr;
        next=nullptr;
    }
};
template<typename T>
struct my_list{
	int list_size;
	Node_list<T> *start,*target;
	my_list(){
		list_size=0;
		start=target=nullptr; 
	}
	Node_list<T>* begin(){
		return start;
	}
	Node_list<T>* end(){
		return target;
	}
	bool empty(){
		return list_size==0;
	}
	int size(){
		return list_size;
	}
	void clear(){
		while(!empty()) pop_front();
	} 
	T at(const int & index_list){
		if(empty()||index_list<0||index_list>list_size) return T();
		int total=1;
		Node_list<T> *list_i;
		if(index_list>list_size-index_list){
			list_i=target;
			while(total<=list_size-index_list){
				list_i=list_i->last;
				total++;
			}
			return list_i->value;
		}
		else{
			list_i=start;
			while(total<index_list){
				list_i=list_i->next;
				total++;
			}
			return list_i->value;
		}
	}
	bool push_front(const T& value){
    	if(list_size+1>LIST_SIZE) return false;
        Node_list<T>* new_node=new Node_list<T>(value);
        if(list_size==0){
            start=target=new_node;
            list_size++;
            return 1;
        }
        new_node->next=start;
        start->last=new_node;
        start=new_node;
        list_size++;
        return 1;
    }
    bool push_back(const T& value){
    	if(list_size+1>LIST_SIZE) return false;
        Node_list<T>* new_node=new Node_list<T>(value);
        if(list_size==0){
            start=target=new_node;
            list_size++;
            return 1;
        }
        new_node->last=target;
        target->next=new_node;
        target=new_node;
        list_size++;
        return 1;
    }
	bool insert(const int & index_list,const T& value){
		if(list_size+1==LIST_SIZE||index_list<0||index_list>list_size+1) return false;
		if(index_list==1){
			push_front(value);	
			return true;
		}
		if(index_list==list_size+1){
			push_back(value);
			return true;
		}
		Node_list<T>* new_node=new Node_list<T>(value);
		if(list_size==0){
			start=target=new_node;
			list_size++;
			return true;
		}
		int total=1;
		Node_list<T> *list_i;
		if(index_list>list_size-index_list+1){
			list_i=target;
			while(total<=list_size-index_list){
				list_i=list_i->last;
				total++;
			}
			new_node->last=list_i->last;
			new_node->next=list_i;
			list_i->last->next=new_node;
			list_i->last=new_node; 
		}
		else{
			list_i=start;
			while(total<index_list-1){
				list_i=list_i->next;
				total++;
			}
			new_node->last=list_i;
			new_node->next=list_i->next;
			list_i->next->last=new_node;
			list_i->next=new_node; 
		}
		list_size++;
		return true;
	}
	bool insert(const T& value,bool (*cmp)(const T&,const T&)=default_list<T>().operator(),const char* & direction="left"){
		if(list_size+1>LIST_SIZE) return false;
		Node_list<T> *new_node=new Node_list<T>(value);
		Node_list<T> *list_i;
		if(direction=="left"){
			list_i=start;
			while(list_i->next!=nullptr&&cmp(list_i->value,list_i->next->value)) list_i=list_i->next;
			new_node->last=list_i;
			new_node->next=list_i->next;
			if(list_i->next!=nullptr) list_i->next->last=new_node;
			else target=new_node;
			list_i->next=new_node; 
		}
		else{
			list_i=target;
			while(list_i->last!=nullptr&&cmp(list_i->value,list_i->last->value)) list_i=list_i->last;
			new_node->next=list_i;
			new_node->last=list_i->last;
			if(list_i->last!=nullptr) list_i->last->next=new_node;
			else start=new_node;
			list_i->next=new_node; 
		}
		list_size++;
		return true;
	}
	bool pop_front(){
        if(list_size==0) return false;
        Node_list<T>* t=start;
        if(list_size==1){
            start=target=nullptr;
            delete t;
            list_size--;
            return true;
        }
        start=start->next;
        start->last=nullptr;
        delete t;
        list_size--;
        return true;
    }
    bool pop_back(){
        if(list_size==0) return false;
        Node_list<T>* t=target;
        if(list_size==1){
            start=target=nullptr;
            delete t;
            list_size--;
            return true;
        }
        target=target->last;
        target->next=nullptr;
        delete t;
        list_size--;
        return true;
    }
    bool erase(const int & index_list){
    	if(list_size==0) return false;
    	if(index_list==1){
    		pop_front();	
    		return true;
		}
    	if(index_list==list_size){
    		pop_back();
    		return true;
		}
    	int total=1;
    	Node_list<T>* list_i;
    	if(index_list>list_size-index_list){
			list_i=target;
			while(total<=list_size-index_list){
				list_i=list_i->last;
				total++;
			}
		}
		else{
			list_i=start;
			while(total<index_list){
				list_i=list_i->next;
				total++;
			}
		}
		list_i->last->next=list_i->next;
		list_i->next->last=list_i->last;
		delete list_i; 
		list_size--;
		return true;
	}
};