Best Coder ^beta
VIP | STD Contests
DIY | Web-DIY ^beta

Boring data structure problem

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1871 Accepted Submission(s): 598

Problem Description

"Why don't you write some background story for this boring data structure problem?"
"Because it's too boring..."

There's a queue(not the original queue one may refer to as a data structure, here a double-ended queue, to be more precise) that is initially empty. Then, there are infinite elements numbered $1,2,\dots$, entering the queue in the order of their numbers(i.e., the first element to enter the queue is numbered $1$, the second, $2$ et cetera). If an element leaves the queue, it will not enter the queue anymore.

Now there are $q$ operations, each in one of the following forms:

Let the next element enter the left end of the queue.

Let the next element enter the right end of the queue.

Let the element numbered $x$ leave the queue.

Ask the number of the element in the middle of the queue. (If there are $m$ elements in the queue currently, you should output the number of the element that is the $\lceil \frac{m+1}{2} \rceil$th from the left).

Input

The first line of each test case contains one number $q(1\leq q \leq 10^7)$, denoting the number of operations.

Then $q$ lines follow, each in one of the following forms:

$L$, denoting the next element enters the left end of the queue

$R$, denoting the next element enters the right end of the queue

$G$ $x$, denoting the element numbered $x$ leaves the queue (It is guaranteed that the element numbered $x$ is in the queue when this operation is applied)

$Q$ denoting a query that asks the number of the element in the middle of the queue(It is guaranteed that the queue is not empty when this operation is applied)

It is guaranteed that the number of operations of the third and the fourth type is both less than $1.5\cdot 10^6$.

Output

For each operation of the fourth kind, output a number in a line, denoting the answer to the query.

Sample Input

9
L
L
L
Q
R
Q
G 1
R
Q

Sample Output

2
1
4

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-19 22:32:09, Gzip enabled

Administration