bookshelf problem

The  library  has  hired you to  manage  its  very  long  bookshelf.

   This  bookshelf  is  infinitely  long  on  both  sides. Your  task,  as  bookshelf  manager,  is  to  put  books  onto  the  bookshelf,  and  remove  them  as  requested. To  keep  the  bookshelf  neat,  all  books  must  be placed  next  to  each  other.

   In  other  words,  there can  never be  an empty  space  between two  books  on the  bookshelf.

 The  following  are  the  tasks  that  the  librarian can ask  you to  do:

 1.  Put a  book  on the  bookshelf,  on  the  left  of  all  the  other  books.
 2.  Put a  book  on the  bookshelf,  on  the  right  of  all  the  other  books.
 3.  Remove  the left-most  book from  the  bookshelf.
 4.  Remove  the right-most  book  from  the  bookshelf.

 In addition  to  these  four  tasks,  the  librarian can ask  you  how  far  a  book  is  from  the  left-most  book  or  rightmost  book  of  the  bookshelf  (see  the  input  section  for  more  details).

 You  will start  with  an  empty  bookshelf.   If  the  bookshelf  is  empty,  tasks  1  and  2  are  equivalent  and  you  can put  the  book  anywhere  on  the  bookshelf.

 Each  book  has  a  unique  identification  number,  d,  where  1  ≤  d  ≤  2^30.

_Input_
 The  input  consists  of  several  lines.   The  first  line  contains  a  single  integer  t,  the  number  of  tasks.   This  is followed  by  t  lines,  each  line  containing  a  task  that  you  have  to  do  immediately.

   There  are  six  tasks, numbered  1  to  6. The  following  describes  the  format  of  the  task  (k  stands for  an  integer):
 •  1 k     – You are given the book  with  identification  number  k,  and you must  put  it  on  the bookshelf,  on  the  left  of  all  the  other  books.
 •  2  k     – You are given the book with  identification  number  k,  and you must  put  it  on  the bookshelf,  on  the  right  of  all  the  other  books.
 •  3     –  Remove the  left-most  book from  the  bookshelf.
 •  4       – Remove the right-most book from  the bookshelf.
 •  5  k     – Print a line containing a  single  integer  n,  where  the  book  with identification number  k  is the  nth  book from  the  left  of  the  bookshelf.
 •  6  k     – Print a line containing a  single  integer  n,  where  the  book  with identification number  k  is the  nth  book from  the  right  of the  bookshelf.

 _Output_
Several  lines,  each  line  contains  a single  integer,  which  is  a response  from either task  5  or 6.