using System;

​

// To execute C#, please define "static void Main" on a class

// named Solution.

​

class Program

{

    static void Main(string[] args)

    {

        var deq = new Deque();

        deq.Push(1);

        deq.Push(2);

        deq.Push(3);

        Console.WriteLine($"{deq.Pop()}");

        Console.WriteLine($"{deq.Pop()}");

        Console.WriteLine($"{deq.Pop()}");

    }

    public class Deque

    {

        class Node

        {

            public Node(int v) {Value = v;}

            public Node _next;

            public Node _prev;

            public int Value;

        }

        private Node _head = null;

        private Node _tail = null;

        public void Push(int v)

        {

            var newNode = new Node(v);

            if (_head == null)

            {

                _head = newNode;

                _tail = _head;

                return;

            }

            newNode._next = _head;

            newNode._prev = null;

            _head._prev = newNode;

            _head = newNode;

            return;

        }

        public int Pop()

        {

            if (_head ==null)

                return Int32.MaxValue;

            var toReturn = _head.Value;

            _head = _head._next;

            if (_head != null)

                _head._prev = null;

            return toReturn;

        }

    }

}