Dynamic maximum sum P59380

In this problem, you have to efficiently keep a vector V with n integers. There is just one update operation: given any position i between 0 and n − 1, and an integer x, set V[i] = x. Appart from that, you have to repeatedly report the maximum sum of all the consecutive subsequences of the current vector.

Input

Input consists of several cases. Every case begins with n, followed by the initial content of V, followed by n operations, each one with a pair i x. You can assume 1 ≤ n ≤ 10⁵, 0 ≤ i < n, and −10¹² ≤ x ≤ 10¹².

Output

For every case, print n+1 numbers: the maximum sum of consecutive elements inside the vector before the first update, and also after every update. Print a line with 10 dashes at the end of each case.