ztm 的最大前缀和

题目描述

ztm 最近对最大前缀和很感兴趣

也就是给出一个包含 $n$ 个数字的序列 $a_i$

先得到 $premax[i]$ = $max(a_1,a_2 \dots a_i)$

然后将 $premax[i]$ 求和 $sum = premax[1] + premax[2] + \dots premax[n]$ 即为最大前缀和

但是 ztm 最近又突发奇想，想着现在不过是静态的求和

如果改成动态的问题呢？

现在 ztm 给出 $m$ 次不同的操作

每次操作用 pos x 来表示修改 $a[pos] = x$

现在 ztm 想知道每次操作以后，整个序列的最大前缀和是多少？

输入格式

第一行输入一个正整数 $n$。

接下来一行 $n$ 个数字 $a_1$ 到 $a_n$。

接下来一行一个数字 $m$。

接下来 $m$ 行，每行两个数字 $pos,x$。

输出格式

输出共 $m$ 行，每行一个数字表示修改以后的最大前缀和。

数据范围

对于 $30\%$ 的数据：$n,m\leq 5000$。

对于 $60\%$ 的数据：$n,m\leq 50000$。

对于 $80\%$ 的数据：$n,m\leq 200000$。

对于 $100\%$ 的数据：$n,m\leq 300000, a_i\leq 10^9$。

样例输入

10
114 357 904 407 100 624 449 897 115 846
20
5 357
6 350
2 939
9 1182
7 1062
2 3300
4 6867
4 2076
3 8458
9 6575
10 5737
10 338
9 10446
4 7615
2 5686
4 10091
1 6466
6 15551
3 10914
7 3234

样例输出

7703
7703
8565
9051
9297
29814
54783
29814
71078
71078
71078
71078
75054
75054
77440
85605
92737
119327
123429
123429