Problem H
Teque
You have probably heard about the deque (double-ended queue) data structure, which allows for efficient pushing and popping of elements from both the front and back of the queue. Depending on the implementation, it also allows for efficient random access to any index element of the queue as well. Now, we want you to bring this data structure up to the next level, the teque (triple-ended queue)!
The teque supports the following four operations:
-
push_back x: insert the element
into the back of the teque. -
push_front x: insert the element
into the front of the teque. -
push_middle x: insert the element
into the middle of the teque. The inserted element now becomes the new middle element of the teque. If is the size of the teque before the insertion, the insertion index for is (using -based indexing). -
get i: prints out the
index element ( -based) of the teque.
Input
The first line contains an integer
Output
For each get i command, print the
value inside the
Warning
The I/O files are large. Please use fast I/O methods.
Sample Input 1 | Sample Output 1 |
---|---|
9 push_back 9 push_front 3 push_middle 5 get 0 get 1 get 2 push_middle 1 get 1 get 2 |
3 5 9 5 1 |