你將要實現一個功能強大的整數序列編輯器。

在開始時，序列是空的。

編輯器共有五種指令，如下：

1、I x，在光標處插入數值 xx。
2、D，將光標前面的第一個元素刪除，如果前面沒有元素，則忽略此操作。
3、L，將光標向左移動，跳過一個元素，如果左邊沒有元素，則忽略此操作。
4、R，將光標向右移動，跳過一個元素，如果右邊沒有元素，則忽略此操作。
5、Q k，假設此刻光標之前的序列為 a1,a2,…,ana1,a2,…,an，輸出 max1≤i≤kSimax1≤i≤kSi，其中 Si=a1+a2+…+aiSi=a1+a2+…+ai。

輸入格式

第一行包含一個整數 QQ，表示指令的總數。

接下來 QQ 行，每行一個指令，具體指令格式如題目描述。

輸出格式

每一個 Q k 指令，輸出一個整數作為結果，每個結果佔一行。

數據範圍

1≤Q≤1061≤Q≤106,
|x|≤103|x|≤103,
1≤k≤n1≤k≤n

輸入樣例：

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

輸出樣例：

2 3

樣例解釋

下圖包含了對樣例的過程描述：

算法助手抓app跳轉url_scheme_ci

解題思路：

解題思路:
{
    1:suml[i]用來記錄左邊堆的前綴和;
    2:suml_max[i]用來記錄前i個前綴和中最大的前綴和
}
1:建立一個對頂棧左右棧頂分別為[0,1,...,tl] [tr, ...., 0];
2:當插入一個元素時，左邊棧增加一個元素右邊棧不變
3:當將光標前面的第一個元素刪除將左邊棧頂的元素刪除，與右邊無關
4:當光標向左移動, 將左邊棧頂放到右邊棧頂
5:當光標向右移動, 將右邊棧頂放到左邊

解題代碼：

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000010;

int suml[N], suml_max[N];
int stkl[N], stkr[N], tl, tr;//stkl為左邊棧，stkr為右邊棧, tl, tr分別為棧頂

void letf_add(int x)
{
    stkl[++ tl] = x;//將x插入左邊棧
    suml[tl] = suml[tl - 1] + x;//計算左邊棧前綴和
    suml_max[tl] = max(suml[tl], suml_max[tl - 1]);//記錄左邊前綴和的最大值
}

int main()
{
    suml_max[0] = -0x3f3f3f3f;
    
    int T;
    cin >> T;
    while (T -- )
    {
        char op[2];
        scanf("%s", op);
        
        if (op[0] == 'I')
        {
            int x;
            cin >> x;
            letf_add(x);
        }
        else if (op[0] == 'D')
        {
            if (tl > 0) tl -- ;//刪除一個元素左邊棧光標向前移動一個位置
        }
        else if (op[0] == 'L')
        {
            if (tl > 0) stkr[++ tr] = stkl[tl -- ];//向左移動將左邊棧頂放入右邊棧頂
        }
        else if (op[0] == 'R')
        {
            if (tr) letf_add(stkr[tr -- ]);//向右移動將右邊棧頂放入左邊棧頂
        }
        else if (op[0] == 'Q')
        {
            int x;
            cin >> x;
            printf("%d\n", suml_max[x]);
        }
    }
    
    return 0;
}