#include <iostream>
using namespace std;

struct Item{
    Item *pPrev;
    int data;
    Item *pNext = nullptr;

    Item(int value){
        pPrev = nullptr;
        data = value;
        pNext = nullptr;
    }
};

struct List{
    Item *pHead = new Item(0);
    Item *pTail = new Item(0);
    int size;

    List(){
        pHead->pNext = pTail;
        pTail->pPrev = pHead;
        size = 0;
    }

    Item *get(int index){
        int curInd = -1;
        Item *pCurrent = pHead;
        while(pCurrent != pTail && curInd != index){
            curInd++;
            pCurrent = pCurrent->pNext;
        }
        return pCurrent;
    }

    Item *insert(int data, int index){
        Item *newItem = new Item(data);

        Item *pPrevItem = get(index-1);
        Item *pNextItem = pPrevItem->pNext;

        pPrevItem->pNext = newItem;
        newItem->pPrev = pPrevItem;
        newItem->pNext = pNextItem;
        pNextItem->pPrev = newItem;

        size++;
        return newItem;
    }

    int remove(int index){
        Item *pItem = get(index);
        int data = pItem->data;

        Item *pPrevItem = pItem->pPrev;
        Item *pNextItem = pItem->pNext;

        delete pItem;
        pPrevItem->pNext = pNextItem;
        pNextItem->pPrev = pPrevItem;

        size--;
        return data;
    }

    int popBack(){
        return remove(count()-1);
    }

    int popFront(){
        return remove(0);
    }

    int count(){
        return size;
    }

    Item *pushBack(int data){
        return insert(data, count());
    }

    Item *pushFront(int data){
        return insert(data, 0);
    }

    void swap(int ind1, int ind2){
        if(abs(ind1-ind2) == 1){
            Item *pItem1 = get(min(ind1, ind2));
            Item *pItem2 = get(max(ind1, ind2));
            Item *pPrevItem = pItem1->pPrev;
            Item *pNextItem = pItem2->pNext;
            pPrevItem->pNext = pItem2;
            pNextItem->pPrev = pItem1;
            pItem1->pPrev = pItem2;
            pItem1->pNext = pNextItem;
            pItem2->pPrev = pPrevItem;
            pItem2->pNext = pItem1;
        }else{
            Item *pItem1 = get(ind1);
            Item *pItem2 = get(ind2);
            Item *pPrev1 = pItem1->pPrev;
            Item *pPrev2 = pItem2->pPrev;
            Item *pNext1 = pItem1->pNext;
            Item *pNext2 = pItem2->pNext;
            pPrev1->pNext = pItem2;
            pPrev2->pNext = pItem1;
            pNext1->pPrev = pItem2;
            pNext2->pPrev = pItem1;
            pItem1->pPrev = pPrev2;
            pItem2->pPrev = pPrev1;
            pItem1->pNext = pNext2;
            pItem2->pNext = pNext1;
        }
    }


    void print(){
        Item *pCurrent = pHead->pNext;
        while(pCurrent != pTail){
            cout << pCurrent->data << endl;
            pCurrent = pCurrent->pNext;
        }
    }

    void printBack(){
        Item *pCurrent = pTail->pPrev;
        while(pCurrent != pHead){
            cout << pCurrent->data << endl;
            pCurrent = pCurrent->pPrev;
        }
    }
};