#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <set>
#include <utility>
#include <map>
#include <string>
#include <exception>
#include <stddef.h>
#include <memory>
#include <list>

using namespace std;

template <typename T>
class Value;

template<typename T>
class LIterator {
public:
    Value<T>* cur;
    LIterator<T>() {
    }
    LIterator<T>(Value<T> * new_cur) {
        cur = new_cur;
    }
    LIterator<T>& operator++() {
        cur = cur->next;
        return (*this);
    }
    const T operator*() const {
        return *cur->field;
    }
    bool operator== (const LIterator<T>& other) {
        return cur == other.cur;
    }
    bool operator != (const LIterator<T>& other) {
        return !(*this == other);
    }
};

template <typename T>
class Value{
public:
    T* field = nullptr;
    struct Value* next = nullptr;
    struct Value* prev = nullptr;
    Value<T>() {
        cout << "default constructor\n";
    }
    ~Value() {
        delete field;
    }
};

template <typename T>
class List{
public:
    Value<T>* fir;
    Value<T>* last;
    Value<T> fake;
    int sz = 0;
    List<T>() {
        cout << "List default constructor\n";
        fir = &fake;
        last = &fake;
        last->prev = fir;
        fir->next = last;
    }
    int size() const {
        return sz;
    }
    void push_back(const T& new_val) {
        if (sz == 0) {
            fir = new Value<T>;
            fir->field = new T(new_val);
            fir->next = last;
            last->prev=  fir;
            ++sz;
            return;
        }
        ++sz;
        Value<T>* cur = new Value<T>;
        cur->field = new T(new_val);
        cur->prev = last->prev;
        cur->next = last;
        last->prev->next = cur;
        last->prev = cur;
    }
    void pop_back() {
        if (sz == 1) {
            delete fir;
            fir = last;
            fir->next = nullptr;
            last->prev = nullptr;
        } else {
            last->prev = last->prev->prev;
            delete last->prev->next;
            last->prev->next = last;
        }
        --sz;
    }
    void push_front(const T& new_val) {
        if (sz == 0) {
            fir = new Value<T>;
            fir->field = new T(new_val);
            fir->next = last;
            last->prev=  fir;
            ++sz;
            return;
        }
        ++sz;
        Value<T>* cur = new Value<T>;
        cur->field = new T(new_val);
        cur->prev = nullptr;
        cur->next = fir;
        fir->prev = cur;
        fir = cur;
    }
    void pop_front() {
        if (sz == 1) {
            delete fir;
            fir = last;
            fir->next = nullptr;
            last->prev = nullptr;
        } else {
            fir = fir->next;
            delete fir->prev;
        }
    }
    LIterator<T> begin() {
        return LIterator<T>(fir);
    }
    LIterator<T> end() {
        return LIterator<T>(last);
    }
    ~List() {
        while (sz) {
            pop_front();
        }
    }
};