#include <iostream>

template<typename T>
class List {
private:
    class ListNodeBase {
    public:
        ListNodeBase* next;
        ListNodeBase* prev;
        ListNodeBase()
            : next(nullptr)
            , prev(nullptr)
        {}
    };
    class ListNode: public ListNodeBase {
    public:
        T value;
        explicit ListNode(const T& val)
            :value(val)
        {}
        ListNode(const ListNode &node) : value(node.value) {}
    };
    size_t count;
    ListNodeBase *head;
    ListNodeBase *tail;

    public:
    class ListIterator {
    private:
        ListNodeBase* current;
        const List* Data;

    public:
        explicit ListIterator(ListNodeBase* cur, const List* data)
            : current(cur)
            , Data(data)
        {}
        const  T& operator * () const {
            return static_cast<ListNode*>(current)->value;
        }
        T& operator * () {
            return static_cast<ListNode*>(current)->value;
        }
        ListIterator& operator++ () {
            current = current->next;
            return *this;
        }
        ListIterator& operator-- () {
            if (current == nullptr) {
                *this = ListIterator(Data->tail, Data);
                return *this;
            }
            current = current->prev;
            return *this;
        }
        bool operator == (const ListIterator& other) const {
            return current == other.current;
        }
        bool operator != (const ListIterator& other) const {
            return current != other.current;
        }
    };

    List() : count(0), head(nullptr), tail(nullptr)
    {}

    List(const List &other) : count(other.count) {
        if (!count) return;
        head = static_cast<ListNodeBase*>
        (new ListNode(static_cast<ListNode*>(other.head)->value));
        ListNodeBase* cur = head;
        ListNodeBase* it = other.head->next;
        while (it != nullptr) {
            ListNodeBase *nxt = static_cast<ListNodeBase*>
            (new ListNode(static_cast<ListNode*>(it)->value));
            cur->next = nxt;
            nxt->prev = cur;
            tail = it;
            cur = cur->next;
            it = it->next;
        }
    }

    List& operator=(const List &other) {
        ListNodeBase *it1 = head;
        while (it1 != nullptr) {
            ListNodeBase *nxt = it1->next;
            delete static_cast<ListNode*>(it1);
            it1 = nxt;
        }
        count = other.count;
        head = static_cast<ListNodeBase*>(new ListNode(static_cast<ListNode*>(other.head)->value));
        ListNodeBase* cur = head;
        ListNodeBase* it = other.head->next;
        while (it != nullptr) {
            ListNodeBase *nxt = static_cast<ListNodeBase*>
            (new ListNode(static_cast<ListNode*>(it)->value));
            cur->next = nxt;
            nxt->prev = cur;
            tail = it;
            cur = cur->next;
            it = it->next;
        }

        return *this;
    }

    ~List() {
        ListNodeBase *it = head;
        while (it != nullptr) {
            ListNodeBase *nxt = it->next;
            delete static_cast<ListNode*>(it);
            it = nxt;
        }
    }

    size_t size() const {
        return count;
    }

    ListIterator begin() const {
        return ListIterator(head, this);
    }
    ListIterator end() const {
        return ListIterator(nullptr, this);
    }

    void push_back(const T &value) {
        if (head == nullptr) {
            tail = head = static_cast<ListNodeBase*>(new ListNode(value));
            count++;
            return;
        }
        ListNodeBase *it = tail;
        ListNodeBase *nlast = static_cast<ListNodeBase*>(new ListNode(value));
        nlast->prev = it;
        it->next = nlast;
        tail = nlast;
        count++;
    }

    void push_front(const T &value) {
        if (head == nullptr) {
            head = static_cast<ListNodeBase*>(new ListNode(value));
            count++;
            return;
        }
        ListNodeBase *nprev = static_cast<ListNodeBase*>(new ListNode(value));
        nprev->next = head;
        head->prev = nprev;
        head = nprev;
        count++;
    }

    void pop_back() {
        if (head == nullptr) return;
        ListNodeBase *last = tail;
        if (last == head) {
            delete static_cast<ListNode*>(head);
            head = nullptr;
            tail = nullptr;
            count = 0;
            return;
        }
        last->prev->next = nullptr;
        tail = last->prev;
        delete static_cast<ListNode*>(last);
        count--;
    }

    void pop_front() {
        if (head == nullptr) return;
        ListNodeBase *nxt = head->next;
        if (nxt != nullptr) {
            nxt->prev = nullptr;
        }
        delete static_cast<ListNode*>(head);
        head = nxt;
        count--;
        if (count == 0) {
            tail = nullptr;
        }
    }
};