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