/*#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("section-anchors")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")*/
#define _CRT_SECURE_NO_WARNINGS
#include <chrono>
#include <set>
#include <map>
#include <deque>
#include <cmath>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
#include <iomanip>
#include <numeric>
#include <time.h>//////////////
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
//#define endl '\n'
#define mp make_pair
#define pbc push_back
#define pob pop_back()
#define empb emplace_back
#define queuel queue<long long>
#define sqr(a) ((a) * (a))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pin(p) cin >> p.first >> p.second;
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define rev(v) reverse(v.begin(), v.end());
#define sout(s, c) for (auto i : s) cout << i << c;
#define pout(p) cout << p.first << " " << p.second;
#define er(v, l, r) erase(v.begin() + l, v.begin() + r);
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
#define vout(v, c) for (int i = 0; i < v.size(); ++i) cout << v[i] << c;
#define pushi(v, a) for (int i = 0; i < a.size(); ++i) v.push_back(a[i]);
#define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); srand(time(NULL))
#define sp system("pause")
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
using namespace std;
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
const ld EPS = 1e-10;
const int inf = 1e9;
const ld PI = acos(-1);
int mod = (int)998244353;
const int MOD7 = 1000000007;
const int MOD9 = 1000000009;
const int a228 = 18;
const ll kekmod = 1791791791;
const ll bestmod = 1148822869;
const ll secmod = (int) 1e9 + 113;
vector<ll> mods = { kekmod,bestmod,mod,MOD9,1000000007 };
vector<ll> hashpows = { 29,31,37,43,47,53,179,229 };
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count() + 228 + 'i' + 'q' + 1337 + 1488);
ll MOD = mods[rnd() % mods.size()];
ll hashpow = hashpows[rand() % hashpows.size()];
#define int ll
struct vertex
{
	int dp[4][4];
	vertex()
	{
		for (int i = 0; i < 4; ++i)for (int j = 0; j < 4; ++j)dp[i][j] = -1e18;
		dp[0][0] = 0;
	}
};
const int MAXN = 4e4 + 1;
vertex t[4 * MAXN];
vertex merge(vertex a, vertex b, int l, int r)
{
	vertex ans = vertex();
	for (int i1 = 0; i1 < 4; ++i1)
	{
		for (int i2 = 0; i2 < 4; ++i2)
		{
			for (int i3 = 0; i3 + i2 < 4; ++i3)
			{
				for (int i4 = 0; i4 < 4; ++i4)
				{
					if (a.dp[i1][i2] < 0 || b.dp[i3][i4] < 0)continue;
					int rght;
					if (i3 + i4 >= r - (l + r) / 2)
					{
						rght = r-(l+r)/2 + i2;
					}
					else
					{
						rght = i4;
					}
					int lft;
					if (i1 + i2 >= (l + r) / 2 - l)
					{
						lft = (l + r) / 2 - l + i3;
					}
					else
					{
						lft = i1;
					}
					if (lft < 4 && rght < 4)
					{
						ans.dp[lft][rght] = max(a.dp[i1][i2] + b.dp[i3][i4], ans.dp[lft][rght]);
					}
				}
			}
		}
	}
	return ans;
}
int a[MAXN];
void build(int v, int l, int r)
{
	if (l == r - 1)
	{
		t[v] = vertex();
		t[v].dp[1][1] = a[l];
		return;
	}
	build(2 * v + 1, l, (l + r) / 2);
	build(2 * v + 2, (l + r) / 2, r);
	t[v] = merge(t[2 * v + 1], t[2 * v + 2], l, r);
}
void upd(int v, int l, int r, int ql, int qr, int x)
{
	if (l >= qr || ql >= r)return;
	if (l >= ql && r <= qr)
	{
		t[v].dp[1][1] = x;
		return;
	}
	upd(2 * v + 1, l, (l + r) / 2, ql, qr, x);
	upd(2 * v + 2, (l + r) / 2, r, ql, qr, x);
	t[v] = merge(t[2 * v + 1], t[2 * v + 2], l, r);
}
int get()
{
	int ans = 0;
	for (int i = 0; i < 4; ++i)for (int j = 0; j + i < 4; ++j)ans = max(ans, t[0].dp[i][j]);
	return ans;
}
signed main()
{
	fastio();
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)cin >> a[i];
	build(0, 0, n);
	cout << get() << endl;
	int q;
	cin >> q;
	while (q--)
	{
		int p, v;
		cin >> p >> v;
		p--;
		a[p] = v;
		upd(0, 0, n, p, p + 1, v);
		cout << get() << endl;
	}
	//sp;
}