Hãy cài đặt một deque (hàng đợi hai đầu) sử dụng mảng vòng (circular array). Deque hỗ trợ các thao tác:

• push_front x: thêm x vào đầu deque.
• push_back x: thêm x vào cuối deque.
• pop_front: xoá và in giá trị phần tử đầu. Nếu rỗng, in -1.
• pop_back: xoá và in giá trị phần tử cuối. Nếu rỗng, in -1.
• front: in giá trị phần tử đầu. Nếu rỗng, in -1.
• back: in giá trị phần tử cuối. Nếu rỗng, in -1.
• size: in số lượng phần tử hiện tại.

Deque dùng mảng vòng (circular buffer) có kích thước cố định MAX = 100000.

Đầu vào

• Dòng đầu tiên chứa số nguyên Q (1 ≤ Q ≤ 10^5).
• Q dòng tiếp theo, mỗi dòng là một thao tác.

Đầu ra

Với mỗi thao tác pop_front, pop_back, front, back, size, in kết quả trên một dòng.

Ví dụ

Input:
12
push_back 1
push_back 2
push_front 3
front
back
pop_front
pop_back
push_front 4
push_back 5
front
pop_front
size

Output:
3
2
3
1
4
4
2