deque.py

class Element():
  def __init__(self, data, next=None, prev=None):
    self.data = data
    self.next = next
    self.prev = prev

class Deque():
  def __init__(self):
    self.first = None
    self.last = None

  def empty(self):
    return not (self.first or self.last)

  def push_front(self, d):
    el = Element(d, self.first)
    if self.empty():
      self.first = self.last = el
    else:
      self.first.prev = self.first = el

  def pop_front(self):
    if self.empty():
      return -1
    else:
      d = self.first.data
      if self.first == self.last:
        self.last = self.first = None
      else:
        self.first = self.first.next
      return d

  def push_back(self, d):
    el = Element(d, self.last)
    if self.empty():
      self.first = self.last = el
    else:
      self.last.next = self.last = el


  def pop_back(self):
    if self.empty():
      return -1
    else:
      d = self.last.data
      if self.first == self.last:
        self.last = self.first = None
      else:
        self.last = self.last.prev
      return d

n = int(input())

deq = Deque()
for i in range(n):
  line = input()
  comand, arg = [int(x) for x in line.split()]
  if comand == 1:
    deq.push_front(arg)
  elif comand == 2:
    if deq.pop_front() != arg:
      print "NO"
      break
  elif comand == 3:
    deq.push_back(arg)
  elif comand == 4:
    if deq.pop_back() != arg:
      print "NO"
      break
  else:
    print ("WTF???")
else:
  print "YES"