13991399 SUSTech Online Judge
Problem 1399 --Edit The Sequence

1399: Edit The Sequence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 554  Solved: 121
[Submit][Status][Web Board]

Description

LowbieH implements a powerful editor for integer sequences.

The sequence is empty when the editor is initialized.

LowbieH creates 5 types of instructions for the editor:

\(I \ x\)  Insert x after the cursor.

\(D\) Delete the element before the cursor

\(L\) Move the cursor left. If the cursor has already been at the begin of the sequence, it will not move.

\(R\) Move the cursor right. If the cursor has already been at the end of the sequence, it will not move.

\(Q \ k\) Suppose that the current sequence \(BEFORE \  the \  cursor\) is {\(a_1\),\(a_2\),...\(a_n\)}. Find \(max_{1 \le i\le k}S_i\) where \(S_i = a_1 + a_2 + .. + a_i\)

Input

And for each case: The first line contains an integer Q, which is the number of instructions. Then next Q lines contains contain an instruction as described above. (1 <= \(Q\) <= \(10^6\), \(|x| \le 1000\) for \(I\) instruction, \(1 \le k \le n\) for \(Q\) instruction)

Output

For each \(Q\) instruction, output the desired value.

Sample Input

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

Sample Output

2
3

HINT


The sequence of sample test case after instructions is as follow(| denotes the cursor):



I 2  [2|]


I -1  [2 -1|]

I 1  [2 -1 1|]

Q 3  [2 -1 1|]

L    [2 -1| 1]

D    [2 | 1]

R    [2 1|]

Q 2 [2 1|]

Source

 

[Submit][Status]