#include <bits/stdc++.h>
using namespace std;

struct Node{
	int val;
	Node *prev, *next;
	Node(int data) : val(data), prev(NULL), next(NULL) {}
	Node(int data, Node *p, Node *n) : val(data), prev(p), next(n) {}
};

class MidStack{
public:
	Node *head, *mid;
	int size;
	
	MidStack(){
		head = mid = NULL;
		size = 0;
	}
	
	void push(int data){
		if(!head){
			head = mid = new Node(data);
			++size;
			return;
		}
		
		head = new Node(data, NULL, head);
		
		head->next->prev = head;
		
		++size;
		
		if(size & 1)
			mid = mid->prev;
	}
	
	int pop(){
		if(!head)
			return -1;
		
		int retVal = head->val;
		
		Node *temp = head;
		head = head->next;
		
		if(head)
			head->prev = NULL;
			
		if(size & 1)
			mid = mid->next;
			
		--size;
		
		delete temp;
		
		return retVal;
	}
	
	int top(){
		if(!head)
			return -1;
		
		return head->val;
	}
	
	int getMid(){
		if(!mid)
			return -1;
		
		return mid->val;
	}
	
	int popMid(){
		if(!mid)
			return -1;
		
		int retVal = mid->val;
		Node *temp = mid;
		
		if(mid->prev)
			mid->prev->next = mid->next;
		
		if(mid->next)
			mid->next->prev = mid->prev;
		
		mid = (size & 1) ? mid->next : mid->prev;
		
		--size;
		
		if(!size)
			head = NULL;
		
		delete temp;
		
		return retVal;
	}
};

int main() {
	int opt, val;
	
	MidStack st;
	
	cout<<"Operations available on Mid Stack are:\n"
	"1. Push element\n2. Pop element\n3. Top element\n"
	"4. Pop mid element\n5. Get mid element\n";
	cout<<"====================================\n";
	
	while(true){
		cin>>opt;
		
		switch(opt){
			case 1:
				cin>>val;
				cout<<"Enter the value to be pushed: "<<val<<"\n";
				st.push(val); 
				break;
			case 2:
				val = st.pop();
				if(val == -1)
					cout<<"The stack is empty!!\n";
				else
					cout<<"The deleted top element is: "<<val<<"\n";
				break;
			case 3:
				val = st.top();
				if(val == -1)
					cout<<"The stack is empty!!\n";
				else
					cout<<"The top element is: "<<val<<"\n";
				break;
			case 4:
				val = st.popMid();
				if(val == -1)
					cout<<"The stack is empty!!\n";
				else
					cout<<"The deleted middle element is: "<<val<<"\n";
				break;
			case 5:
				val = st.getMid();
				if(val == -1)
					cout<<"The stack is empty!!\n";
				else
					cout<<"The middle element is: "<<val<<"\n";
				break;
			case 6:
				exit(0);
		}
		cout<<"====================================\n";
	}
	
	return 0;
}