#include <bits/stdc++.h>
using namespace std;
class DLLNode
{
public:
    int data;
    DLLNode *next, *prev;
    DLLNode(int n) : data(n), next(nullptr), prev(nullptr) {}
};
class DLL
{
public:
    DLLNode *head;
    DLL()
    {
        head = nullptr;
    }
    bool empty()
    {
        return head == nullptr;
    }
    void InsertFromHead(int value)
    {
        // 1-declare a newnode and init with value
        DLLNode *new_node = new DLLNode(value);
        // 2-check if the list is empty--true--> head = newnode and terminate
        if (empty())
        {
            head = new_node;
            return;
        }
        // insert
        // 1-newnode points to head
        new_node->next = head;
        // 2-the prev of head point to newnode
        head->prev = new_node;
        // 3-move the head to newnode
        head = new_node;
    }
    void InsertFromTail(int value)
    {
        // 1-declare a newnode and init with value
        DLLNode *new_node = new DLLNode(value);
        // 2-check if the list is empty--true--> head = newnode and terminate
        if (empty())
        {
            head = new_node;
            return;
        }
        // 3- declare a temp and move to the last element
        DLLNode *temp = head;
        while (temp->next)
        {
            temp = temp->next;
        }
        // insert
        // 1-prev of new point to the last elemtn
        new_node->prev = temp;
        // 2-last element point to the newelement
        temp->next = new_node;
    }
        void InsertPos(int value, int pos)
    {
        // 1-declare a newnode and init with value
        DLLNode *new_node = new DLLNode(value);
        // 2-check if the list is empty true--> head = newnode and terminate
        if (empty())
        {
            head = new_node;
            return;
        }
        // 3-pos > size pos = size
        //  if(pos>sz) pos = sz;
        // 4-declare a temp ptr and iterat till the pos
        DLLNode *temp = head;
        for (int i = 1; i < pos - 1; temp = temp->next, i++)
            ;
        // شبك الجديد الاول
        //  1- newnode points to what the elemrnt in pos points
        new_node->next = temp->next;
        // 2- the prev of newnode points to the element in the pos
        new_node->prev = temp;
        // القديم بقاا
        //  1- pos points to new node
        temp->next = new_node;
        // 2- the prev of what the new node points make it point to new node
        temp->next->prev = new_node;
    }
    int sz()
    {
        int cntr = 0;
        if (empty())
        {
            return cntr;
        }
        DLLNode *temp = head;

        while (temp)
        {
            cntr++;
            temp = temp->next;
        }
        return cntr;
    }
    bool IsFound(int n)
    {
        bool ret = false;
        if (empty())
            return ret;
        DLLNode *temp = head;
        while (temp)
        {
            if (temp->data == n)
            {
                ret = true;
                break;
            }
            temp = temp->next;
        }
        return ret;
    }
    int RemoveFromHead()
    {
        // check if it is empty--> terminate
        int delval = -1;
        if (empty())
        {
            return delval;
        }
        // check if this element is the last in the list
        if (head->next == nullptr)
        {
            delval = head->data;
            delete head;
            head = nullptr;
            return delval;
        }
        // store the the first node and its value
        DLLNode *delptr = head;
        delval = delptr->data;
        // make the prev of the node after points to null
        head->next->prev = nullptr;
        // move head to this node
        head = head->next;
        delete delptr;
        return delval;
    }
    int RemoveFromTail()
    {
        // check if it is empty--> terminate
        int delval = -1;
        if (empty())
        {
            return delval;
        }
        // check if this element is the last in the list
        if (head->next == nullptr)
        {
            delval = head->data;
            delete head;
            head = nullptr;
            return delval;
        }
        // declare temp node iterat till the last;
        DLLNode *temp = head;
        while (temp->next)
        {
            temp = temp->next;
        }
        delval = temp->data;
        // store the the last node node and its value in delptr and its value in delval
        // the next of the node before equal nullptr
        temp->prev->next = nullptr;
        delete temp;
        return delval;
    }
    int RemovePos(int n, int pos)
    {
        // empty list or the n is not in the list
        int delval = -1;
        if (empty() or !IsFound(n))
        {
            return delval;
        }
        // this is only one element in list
        if (head->next == nullptr)
        {
            delval = head->data;
            delete head;
            head = nullptr;
            return delval;
        }
        // if(pos > sz) pos = sz;
        DLLNode *temp = head;
        // store the elemt in posistion pos
        for (int i = 1; i < pos; i++, temp = temp->next);
        DLLNode *delptr = temp;
        delval = delptr->data;
        // 1- cut the conection betw the pos and the node befor and make the node before to point
        // to the node after the pos node
        if(temp->prev)
            temp->prev->next = temp->next;
        // 2 cut the connection between the node after and make the prev of node after to point
        //  the node before pos node
        //  this condetion as the pos may be the last since this next is nullptr ????!!!!! nullptr->prev errror
        if (temp->next) {
           temp->next->prev = temp->prev;
            if(!temp->prev) {
                head = head->next;
            }
        }
        // 3- finally delete the pos node
        delete delptr;
        return delval;
    }
    void print()
    {
        if (empty())
        {
            return;
        }
        DLLNode *temp = head;
        while (temp)
        {
            cout << temp->data << ' ';
            temp = temp->next;
        }
        cout << '\n';
    }
};
int main()
{
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
#endif

#ifdef ONLINE_JUDGE

#endif
    DLL dll;

    // Insert at head
    dll.InsertFromHead(10);
    dll.InsertFromHead(20);
    dll.InsertFromHead(30);
    cout << "After inserting at head (30, 20, 10):\n";
    DLLNode *temp = dll.head;
    dll.print();

    // Insert at tail
    dll.InsertFromTail(5);
    dll.InsertFromTail(1);
    cout << "After inserting at tail (5, 1):\n";
    dll.print();

    // Insert at position
    dll.InsertPos(15, 2); // Insert 15 at position 2
    cout << "After inserting 15 at position 2:\n";
    dll.print();

    // Remove from head
    cout << "Removing from head: " << dll.RemoveFromHead() << "\n";
    cout << "List after removing from head:\n";
    dll.print();

    // Remove from tail
    cout << "Removing from tail: " << dll.RemoveFromTail() << "\n";
    cout << "List after removing from tail:\n";
    dll.print();

    // Check if element is found
    int searchValue = 15;
    cout << "Is " << searchValue << " found? " << (dll.IsFound(searchValue) ? "Yes" : "No") << "\n";

    // Remove a specific position
    int removePos = 1;
    cout << "Removing element at position " << removePos << ": " << dll.RemovePos(15, removePos) << "\n";
    cout << "List after removing position " << removePos << ": ";
    dll.print();

    return 0;
}