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^{5},
0 ≤ i < n,
and −10^{12} ≤ x ≤ 10^{12}.

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
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++