Dynamic maximum sum (2) P84977

Here, you have to efficiently keep a list of integer numbers, which is initially empty. Let the current list be x₀, …, x_n−1. There are just two operations:

• Given an integer x and any position j between 0 and n, insert x before the j-th position (at the end, if j = n). That is, the new list must be x₀, …, x_j−1, x, x_j, …, x_n−1.
• Report the maximum sum of all the consecutive subsequences of the list.

Input

Input consists of several cases. Every case begins with the number of operations m, followed by the m operations. We have an M for reporting the maximum, and I x j for inserting. Assume 1 ≤ m ≤ 2 · 10⁵, −10¹² ≤ x ≤ 10¹², and that j is between 0 and the current list size.

Output

For every case, and for every M operation, print the maximum sum of consecutive elements inside the current list. Print a line with 10 dashes at the end of each case.