Problem About Solving Problems (Dequery)
Time limit1sMemory limit512 MB
Maintain a deque under queries that push the same value many times at either end, pop many elements, and read the k-th element; output each read.
- Level
Medium6 of 10
- Topics
- Linked list, Implementation, Simulation, Array
- Solved
- No attempts yet
Problem
You cannot submit to this problem. Refer to the "Problem About Solving Problems" problem.
You are given an empty deque Q. Write a program that executes Q queries. Each query has one of the following forms.
- 1 x k: insert the integer x at the front of the deque k times.
- 2 x k: insert the integer x at the back of the deque k times.
- 3 k: remove k numbers from the front of the deque.
- 4 k: remove k numbers from the back of the deque.
- 5 k: print the number at position k from the front of the deque.
Input
The first line gives the number of queries Q. (Q ≤ 100,000) Each of the next lines contains one query.
For queries 1 and 2, 1 ≤ x, k ≤ 109.
For queries 3, 4, and 5, k is at least 1 and at most the current number of elements in the deque.
Query 5 is given at least once.
Output
For each query 5, print the answer on its own line.