#include <iostream>
#include <any>

template <typename T>
struct Node
    {
        T value;
        Node<T>* next = nullptr;
        Node<T>* prev = nullptr;
    };

template <typename T>
class List
{
    protected:
    Node<T>* start = nullptr;
    Node<T>* end = nullptr;

    Node<T>* getNode(int index)
    {
        if (index >= lenght)
            throw "index > lenght";
        Node<T>* currentNode = start;
        for(int i = 0; i < index; i++) {
            currentNode = currentNode->next;
        }
        return currentNode;
    }

    public:
    int lenght;

    List()
    {
        Node<T>* start = nullptr;
        Node<T>* end = nullptr;
        lenght = 1;
    }

    ~List()
    {
        Node<T>* currentNode = start;
        if (currentNode == nullptr) return;
        while (currentNode->next!=nullptr)
        {
            currentNode = currentNode->next;
            delete currentNode->prev;
        }
        delete currentNode;
    }

    virtual void add(T value)
    {
        Node<T>* node = new Node<T>;
        node->value = value;
        if(start==nullptr) {
            start = node;
            end = node;
            return;
        }
        node->prev = end;
        end->next = node;
        end = node;
        lenght++;
    }

    virtual void add(T value, int index)
    {
        Node<T>* node = new Node<T>;
        node->value = value;

        Node<T>* before = getNode(index-1);
        node->next = before->next;
        node->prev = before;
        node->next->prev = node;
        before->next = node;
        lenght++;
    }

    virtual T pop()
    {
        T result = end->value;
        if (end == start) {
            end = nullptr;
            start = nullptr;
            lenght--;
            return result;
        }
        end = end->prev;
        end->next = nullptr;
        lenght--;
        return result;
    }

    virtual T pop(Node<T>* node)
    {
        node->next->prev = node->prev;
        node->prev->next = node->next;
        lenght--;
        return node->value;
    }

    virtual T pop(int index)
    {
        T result;
        if (index==0) {
            result = start->value;
            start = getNode(index+1);
            lenght--;
        }
        if (index>=lenght-1) {
            result = pop();
        }
        Node<T>* node = getNode(index);
        result = pop(node);
        return result;
    }

    T operator[](int index)
    {
        return getNode(index)->value;
    }

    friend std::ostream &operator <<(std::ostream &os, List &c)
    {
        os << "( ";
        Node<T>* currentNode = c.start;
        while (currentNode->next!=nullptr)
        {
            os << currentNode->value << " = ";
            currentNode = currentNode->next;
        }
        os << currentNode->value << " )";
        return os;
    }
};