8

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long

const int MAX_N = 40000;
const ll INF = (ll) 1e18;

ll a[MAX_N];
vector<vector<vector<ll>>> ans(MAX_N, vector<vector<ll>>(4, vector<ll>(4)));

inline void update(int n, int l, int r) {
	int m = (l + r) / 2;
	for (int l1 = 0; l1 <= 3; l1++)
		for (int r1 = 0; r1 <= 3; r1++)
			ans[n][l1][r1] = -INF;
	for (int l1 = 0; l1 <= 3; l1++)
		for (int r1 = 0; r1 <= 3; r1++)
			if (ans[2 * n + 1][l1][r1] >= 0)
				for (int l2 = 0; l2 + r1 <= 3; l2++)
					for (int r2 = 0; r2 <= 3; r2++)
						if (ans[2 * n + 2][l2][r2] >= 0) {
							int curl = l1;
							if (l1 == m - l)
								curl += l2;
							int curr = r2;
							if (r2 == r - m)
								curr += r1;
							if (curl <= 3 && curr <= 3)
								ans[n][curl][curr] = max(ans[n][curl][curr], ans[2 * n + 1][l1][r1] + ans[2 * n + 2][l2][r2]);
						}
}

void build(int n, int l, int r) {
	if (r - l == 1) {
		for (int l1 = 0; l1 <= 3; l1++)
			for (int r1 = 0; r1 <= 3; r1++)
				ans[n][l1][r1] = -INF;
		ans[n][0][0] = 0;
		ans[n][1][1] = a[l];
	}
	else {
		int m = (l + r) / 2;
		build(2 * n + 1, l, m);
		build(2 * n + 2, m, r);
		update(n, l, r);
	}
}

void change(int n, int l, int r, int pos, int val) {
	if (r - l == 1) {
		a[pos] = val;
		for (int l = 0; l <= 3; l++)
			for (int r = 0; r <= 3; r++)
				ans[n][l][r] = -INF;
		ans[n][0][0] = 0;
		ans[n][1][1] = a[l];
	}
	else {
		int m = (l + r) / 2;
		if (pos < m)
			change(2 * n + 1, l, m, pos, val);
		else
			change(2 * n + 2, m, r, pos, val);
		update(n, l, r);
	}
}

inline ll genans() {
	ll ans1 = 0;
	for (int l = 0; l <= 3; l++)
		for (int r = 0; l + r <= 3; r++)
			ans1 = max(ans1, ans[0][l][r]);
	return ans1;
}

int32_t main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	build(0, 0, n);
	cout << genans() << '\n';

	int q;
	cin >> q;
	for (; q > 0; q--) {
		int pos, val;
		cin >> pos >> val;
		change(0, 0, n, pos - 1, val);
		cout << genans() << '\n';
	}
}