덱

• '덱'을 이용해서 기본적인 연산들을 수행할수 있는지 물어보는 기본 문제. 유사품으로 스택, 큐이 있다.
• 파이썬에서는 collections.deque를 이용해서 주어진 연산들을 처리해주면 된다
• 주어진 연산들은 덱에서 모두 O(1)에 처리되므로 총 시간복잡도는 O(n).

"""Solution code for "BOJ 10866. 덱".

- Problem link: https://www.acmicpc.net/problem/10866
- Solution link: http://www.teferi.net/ps/problems/boj/10866

Tags: [deque]
"""

import collections
import sys


def main():
    N = int(sys.stdin.readline())
    deq = collections.deque()
    for _ in range(N):
        oper = sys.stdin.readline().split()
        op = oper[0]
        if op == 'push_front':
            deq.appendleft(oper[1])
        elif op == 'push_back':
            deq.append(oper[1])
        elif op == 'pop_front':
            print(deq.popleft() if deq else '-1')
        elif op == 'pop_back':
            print(deq.pop() if deq else '-1')
        elif op == 'size':
            print(len(deq))
        elif op == 'empty':
            print('0' if deq else '1')
        elif op == 'front':
            print(deq[0] if deq else '-1')
        elif op == 'back':
            print(deq[-1] if deq else '-1')


if __name__ == '__main__':
    main()