---

#include <iostream>

//struct Node {
//	int data;
//	Node* next;
//	Node(int val) : data(val), next(nullptr) {}
//};
//
//class LinkedList {
//	Node* head;
//	int sz;
//public:
//	LinkedList() : head(nullptr), sz(0) {}
//
//	void push_front(int val) {
//		Node* newNode = new Node(val);
//		newNode->next = head;
//		head = newNode;
//		sz++;
//	}
//
//	void push_back(int val) {
//		Node* newNode = new Node(val);
//		if (!head) {
//			head = newNode;
//		}
//		else {
//			Node* cur = head;
//			while (cur->next) cur = cur->next;
//			cur->next = newNode;
//		}
//		sz++;
//	}
//	void pop_front() {
//		if (!head) return;
//		Node* tmp = head;
//		head = head->next;
//		delete tmp;
//		sz--;
//	}
//
//	int size() const {
//		return sz;
//	}
//
//	void print() const {
//		Node* cur = head;
//		while (cur) {
//			std::cout << cur->data << "  ";
//			cur = cur->next;
//		}
//		std::cout << "\n";
//	}
//	void insert(int pos, int val) {
//		if (pos < 0 || pos > sz) return;
//		if (pos == 0) { push_front(val); }
//
//		Node* cur = head;
//		for (int i = 0; i < pos - 1; i++) cur = cur->next;
//
//		Node* newNode = new Node(val);
//		newNode->next = cur->next;
//		cur->next = newNode;
//		sz++;
//	}
//
//	void remove(int val) {
//		if (!head) return;
//		if (head->data == val) { pop_front(); return; }
//
//		Node* cur = head;
//		while (cur->next && cur->next->data != val)
//			cur = cur->next;
//
//		if (cur->next) {
//			Node* tmp = cur->next;
//			cur->next = tmp->next;
//			delete tmp;
//			sz--;
//		}
//
//
//	}
//
//	~LinkedList() {
//		while (head) pop_front();
//	}
//};
//
//int main() {
//	LinkedList list;
//	list.push_back(1);
//	list.push_back(2);
//	list.push_back(3);
//	list.push_front(0);
//	list.push_front(-1);
//	list.remove(2);
//	list.insert(3, 228);
//	list.print();
//	list.pop_front();
//	list.print();
//	std::cout << list.size() << "\n";
//}


struct Node {
	int data;
	Node* prev;
	Node* next;
	Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
	Node* head;
	Node* tail;
	int sz;

public:
	DoublyLinkedList(): head(nullptr),tail(nullptr), sz(0){}

	void push_front(int val) {
		Node* newNode = new Node(val);
		if (!head) {
			head = tail = newNode;
		}
		else {
			newNode->next = head;
			head->prev = newNode;
			head = newNode;
		}
		sz++;
	}

	void push_back(int val) {
		Node* newNode = new Node(val);
		if (!tail) {
			head = tail = newNode;
		}
		else {
			newNode->prev = tail;
			tail->next = newNode;
			tail = newNode;
		}
		sz++;
	}

	void pop_front() {
		if (!head) return;
		Node* tmp = head;
		head = head->next;
		if (head) head->prev = nullptr;
		else tail = nullptr;
		delete tmp;
		sz--;
		}
	}



};