class clist(object):
  """double-linked list implementation with sentinel"""
  
  def __init__(self):
    """create an empty list in O(1)"""
    self.__len = 0
    self.__sentinel = node()
    self.__sentinel._next = self.__sentinel
    self.__sentinel._prev = self.__sentinel

  def __len__(self):
    """return the length of the list in O(1)"""
    return self.__len
  
  def __contains__(self,x):
    """return if x is in the list in O(N)"""
    return self.__contains_aux(x,self.__sentinel._next)

  def __contains_aux(self,x,nd):
    """auxiliary search function in O(N)"""
    ans = None
    if nd == self.__sentinel:
      ans = False
    elif nd._val == x:
      ans = True
    else:
      ans = self.__contains_aux(x,nd._next)
    return ans

  def __str__(self):
    """return the string representation of the list in O(N)"""
    ans = list()
    self.__str_aux(ans,self.__sentinel._next)
    return str(ans)

  def __str_aux(self,ans,nd):
    if nd != self.__sentinel:
      ans.append(nd._val)
      self.__str_aux(ans,nd._next)
                
  def insert_last(self,x):
    """insert an element to the end of the list in O(1)"""
    prev = self.__sentinel._prev
    nd = node(prev,x,self.__sentinel)
    prev._next = self.__sentinel._prev = nd
    self.__len += 1

  def insert_first(self,x):
    """insert an element to the head of the list in O(1)"""
    nxt = self.__sentinel._next
    nd = node(self.__sentinel,x,nxt)
    nxt._prev = self.__sentinel._next = nd
    self.__len += 1

  def remove_last(self):
    """delete the element last in the list, if any in O(1)"""
    assert not(self.is_empty())
    last = self.__sentinel._prev
    prev = self.__sentinel._prev = last._prev
    prev._next = self.__sentinel
    last._next = last._prev = None
    self.__len -= 1
    
  def remove_first(self):
    """delete the element first in the list, if any in O(1)"""
    assert not(self.is_empty())
    first = self.__sentinel._next
    nxt = self.__sentinel._next = first._next
    nxt._prev = self.__sentinel
    first._next = first._prev = None
    self.__len -= 1
    
  def is_empty(self):
    """return if the list is empty in O(1)"""
    return self.__len==0
  
  def get_last(self):
    """return the element last in the list, if any, in O(1)"""
    assert not(self.is_empty())
    return self.__sentinel._prev._val

  def get_first(self):
    """return the element first in the list, if any, in O(1)"""
    assert not(self.is_empty())
    return self.__sentinel._next._val

    
class node(object):
  """node implementation with previous, value, and next fields"""

  def __init__(self,prev=None,val=None,nxt=None):
    """creates an empty node in O(1)"""
    self._prev = prev
    self._val = val
    self._next = nxt

  def __str__(self):
    """return the string representation of the node in O(1)"""
    return self._val


class stack(object):
  """stack implementation using deep embedding on double-linked list
  implementation with sentinel from clist

  """
  
  def __init__(self):
    """creates an empty stack in O(1)"""
    self.__stack = clist()

  def __len__(self):
    """return the number of elements in the stack in O(1)"""
    return len(self.__stack)

  def push(self,x):
    """adds x to the top of the stack in O(1)"""
    self.__stack.insert_last(x)

  def top(self):
    """return the element last inserted in the stack in O(1)"""
    assert len(self)>0
    return self.__stack.get_last()

  def pop(self):
    """remove the element last inserted in the stack in O(1)"""
    assert len(self)>0
    self.__stack.remove_last()

  def __str__(self):
    """return the string representation of the stack in O(N)"""
    return str(self.__stack)