题目描述

老师给壮壮布置了一个任务，需要他生成一个数列编辑器。

一开始，数列为空，光标在开头位置，编辑器能进行如下 $5$ 种操作：

$I$ $x$：在光标的后面插入一个数 $x$，并把光标移到新加入的 $x$ 后；

$D$：删除光标前的最后一个位置（保证存在），光标位置不变；

$L$：光标左移一位，如果已经在开头则不用做任何事；

$R$：光标右移一位，如果已经在结尾不用做任何事；

$Q$ $l$ $r$：编辑器需要给出 $A[l],A[l+1],A[l+2].....A[r](l \le r)$ 的最大前缀和，保证 $l≤r≤n,n$ 为当前光标前的数字个数。

输入格式

第一行一个整数 $q$，表示操作的总次数；

后 $q$ 行每行是上列五种操作中的某一种。

输出格式

对每个 $Q$ 操作，输出一行表示一个整数表示答案。

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

2
3

样例解释

每次操作结果如下

$I$ $2$ : $[2]$光标在第一个数字后面

$I$ $-1$ : $[2.-1]$光标在第二个数字后面

$I$ $1$ : $[2,-1,1]$光标在第三个数字后面

$Q$ $1$ $3$ : 最大前缀和是$2$

$L$ : $[2,-1,1]$光标在第二个数字后面

$D$ : $[2,1]$光标在第一个数字后面

$R$ : $[2,1]$光标在第二个数字后面

$Q$ $1$ $2$ : 最大前缀和是$3$

数据范围

$30\%$ : 操作种类 : $I$, $Q$ $≤200000$；

另有 $20\%$ : $l$ 恒等于$1$；

$100\%$ : 操作种类 : $I, Q, L, R, D, l$ $≤100000$，$-1000≤x≤1000$。