P2201 Sequence Editor

Xiao Z is an elementary school student who loves math. Recently, he has been studying properties of integer sequences. To facilitate his research, Xiao Z wants to implement a sequence editor called "Open Continuous Lines Processor". At the beginning, the sequence editor contains no numbers, only a cursor. This sequence editor needs to support five operations. - `I x` Insert the number $x$ immediately before the cursor. - `D` Delete the number immediately before the cursor. - `L` Move the cursor one position to the left. - `R` Move the cursor one position to the right. - `Q k` Let the sequence before the cursor be $\{a_1, a_2, \cdots, a_n\}$. Output the maximum prefix sum among the first $k$ positions, i.e., $\max_{1 \le i \le k} \sum_{j=1}^{i} a_j$. It is guaranteed that $k \leqslant n$.

The first line contains an integer $N$, indicating the number of operations. Then follow $N$ lines, each containing one command.

For each `Q k` command, output an integer representing the answer to that operation.

Constraints For $50\%$ of the testdata, $N \leqslant 1000$. For $80\%$ of the testdata, $N \leqslant 10^5$. For $100\%$ of the testdata, $N \leqslant 10^6$, and the absolute value of each inserted number does not exceed $1000$. It is guaranteed that the `D` operation will not be performed when the sequence editor is empty. Translated by ChatGPT 5