# Dynamic maximum sum P59380

Statement html

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 ≤ 105, 0 ≤ i < n, and −1012x ≤ 1012.

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.

Public test cases
• Input

```3
10 5 10
0 -3
1 -8
0 20

1
-300
0 0

3
1000000000000 1000000000000 1000000000000
1 -1
2 -1000000000000
2 2
```

Output

```25
15
10
22
----------
0
0
----------
3000000000000
1999999999999
1000000000000
1000000000001
----------
```
• Information
Author