T563191 线段树 - 最大子段和

给定长度为 $n$ 的数列 $a_1, \dots , a_n$ ，请计算这个数列的最大子段和。 你还需要处理 $q$ 次修改操作。每次操作将数列中第 $p$ 个元素 $a_p$ 修改为 $x$，你需要在每次修改后各计算一次数列的最大子段和。

第一行输入一个正整数 $n \ (1 \le n \le 10^5)$ ； 第二行输入 $n$ 个整数 $a_1, \dots , a_n \ (-10^9 \le a_i \le 10^9)$ ； 接下来一行输入一个整数 $q \ (1 \le q \le 10^5)$ ； 接下来 $q$ 行，每行输入两个正整数 $p, x \ (1 \le p \le n, -10^9 \le x \le 10^9)$ 。

输出 $q + 1$ 行，每行一个整数，表示最初以及每次修改后，数列的最大子段和。