Time Limits: 1000 ms Memory Limits: 65536 KB

Description

这个假期，小h在自家院子里种了许多花，它们围成了一个圈，从1…n编号（n<=100000），小h 对每盆花都有一个喜好值xi,（-1000<=xi<=1000）,小h现在觉得这样一成不变很枯燥，于是他做了m(m<=100000)个改动，每次把第ki盘花改成喜好值为di的花，然后小h要你告诉他，在这个花圈中，连续的最大喜好值是多少。

Input

第一行，n，花盆的数量
第二行，n个数，表示对于每盆花的喜好值。
第三行：m, 改动的次数
以下m行，每行两个数ki 和di 。

Output

M行，每一行对应一个更改，表示连续的最大喜好值，且不能整圈都选。（注意：是在圈上找）

Sample Input

1
2
3
4
5
6
7
5
3 -2 1 2 -5
4
2 -2
5 -5
2 -4
5 -1

Sample Output

1
2
3
4
4
4
3
5

Data Constraint

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct Tree {
	#define lson (x << 1)
	#define rson (x << 1) + 1
	int presum_Max[MAXN << 2], sufsum_Max[MAXN << 2], Max[MAXN << 2];
	int presum_Min[MAXN << 2], sufsum_Min[MAXN << 2], Min[MAXN << 2];
	int sum[MAXN << 2], Min_val[MAXN << 2], rt;
	
	inline void pushup (int x) {
		presum_Max[x] = max (presum_Max[lson], sum[lson] + presum_Max[rson]);
		sufsum_Max[x] = max (sufsum_Max[rson], sufsum_Max[lson] + sum[rson]);
		presum_Min[x] = min (presum_Min[lson], sum[lson] + presum_Min[rson]);
		sufsum_Min[x] = min (sufsum_Min[rson], sufsum_Min[lson] + sum[rson]);
		sum[x] = sum[lson] + sum[rson];
		Max[x] = max (Max[lson], Max[rson]);
		Max[x] = max (Max[x], sufsum_Max[lson] + presum_Max[rson]);
		Min[x] = min (Min[lson], Min[rson]);
		Min[x] = min (Min[x], sufsum_Min[lson] + presum_Min[rson]);
		Min_val[x] = min (Min_val[lson], Min_val[rson]);
		return;
	}
	void insert (int x, int l, int r) {
		if (l == r) {
			scanf ("%d", &sum[x]);
			presum_Max[x] = sum[x];
			sufsum_Max[x] = sum[x];
			presum_Min[x] = sum[x];
			sufsum_Min[x] = sum[x];
			Max[x] = sum[x];
			Min[x] = sum[x];
			Min_val[x] = sum[x];
			return;
		}
		int mid = (l + r) >> 1;
		insert (lson, l, mid);
		insert (rson, mid + 1, r);
		pushup(x);
		return;
	}
	void change (int x, int l, int r, int k, int val) {
		if (l == r) {
			sum[x] = val;
			presum_Max[x] = val;
			sufsum_Max[x] = val;
			presum_Min[x] = val;
			sufsum_Min[x] = val;
			Max[x] = val;
			Min[x] = val;
			Min_val[x] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (k > mid) {
			change (rson, mid + 1, r, k, val);
		}
		else {
			change (lson, l, mid, k, val);
		}
		pushup(x);
		return;
	}
};
Tree T;
int n, m;
int main() {
	scanf ("%d", &n);
	T.rt = 1;
	T.insert (T.rt, 1, n);
	scanf ("%d", &m);
	for (int i = 1; i <= m; i++) {
		int k, val;
		scanf ("%d%d", &k, &val);
		T.change (T.rt, 1, n, k, val);
		int temp;
		if (T.sum[T.rt] != T.Max[T.rt]) {
			temp = T.Max[T.rt];
		}
		else {
			temp = T.sum[T.rt] - T.Min_val[T.rt];
		}
		printf ("%d\n", max (temp, T.sum[T.rt] - T.Min[T.rt]));
	}
	return 0;
}