#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 3e5 + 5;
const int is_query = (1ll << 62);
int state(int a, int b) {
	if (a > b) return 1;
	if (a < b) return -1;
	return 0;
}
struct ConvexHullTrick {
	//To obtain minimum simply insert negative m and bs instead of their true values.
	struct Line {
		int m, b;
		mutable function<const Line*()> succ;
		Line(int m, int b): m(m), b(b) {};
		bool operator<(const Line &other) const {
			if (other.b != is_query) return m < other.m;
			const Line* s = succ();
	        	if (!s) return false;
	        	int x = other.m;
	        	return b - s->b < (s->m - m) * x;
		}
	};
	multiset<Line> s;
	void init() {
		s.clear();
	}
	bool bad(multiset<Line>::iterator x) {
		auto z = next(x);
		if (x == s.begin()) {
			if (z == s.end()) return false;
			return x->m == z->m && x->b <= z->b;
		}
		auto y = prev(x);
		if (z == s.end()) return x->m == y->m && x->b <= y->b;
//		return (y->b - x->b) * (z->m - x->m) >= (x->b - z->b) * (x->m - y->m);
		int l1 = state(y->b, x->b), l2 = state(z->m, x->m), r1 = state(x->b, z->b), r2 = state(x->m, y->m);
		int lft = l1 * l2, rgt= r1 * r2;
		if (lft == 0 && rgt == 0) return true;
		if (lft != rgt) return lft>rgt;
		long double val1 = (long double)(y->b - x->b) / (x->b - z->b);
		long double val2 = (long double)(x->m - y->m) / (z->m - x->m);
		if (lft == 1 && rgt == 1) return val1 >= val2;
		else return val1 <= val2;	
	}
	void add_line(int m, int b) {
		auto x = s.insert(Line(m,b));
		x->succ = [=] { return next(x) == s.end() ? 0 : &*next(x); };
		if (bad(x)) { s.erase(x); return; }
		while (next(x) != s.end() && bad(next(x))) s.erase(next(x));
		while (x != s.begin() && bad(prev(x))) s.erase(prev(x));
	}
	int query(int x) {
		if (s.size() == 0) return 0;
		auto found = *s.lower_bound(Line(x, is_query));
		return found.m * x + found.b;
	}
} ch, chL, chR;
int n, a[N], m, pre[N], suf[N], preSum[N], sufSum[N], ans[N], cuba[N];
void solve(int l, int r) {
	if (l == r) {
		ans[l] = max(ans[l], 2 - 2 * a[l] + (l ? 2 * pre[l - 1] : 0) + 2 * suf[l + 1]);
		return;
	};
//	cout << "l = " << l << " r = " << r << "\n";
	int m = (l + r) >> 1;
	chL.init(), chR.init();
	fw (i, l, m + 1) {
		chL.add_line(-2 * i, i * i - 3 * i + (i ? 2 * preSum[i - 1] : 0) + (i ? 2 * pre[i - 1] : 0));
	}
	fw (i, m + 1, r + 1) {
		chR.add_line(-2 * i, i * i + 3 * i - 2 * preSum[i] + 2 * suf[i + 1]);
	}
	fw (i, l, r + 1) cuba[i] = -infll;
	fw (i, l, m + 1) {
		cuba[i] = max(cuba[i], (i > l ? cuba[i - 1] : -infll));
		cuba[i] = max(cuba[i], chR.query(i) + i * i - 3 * i + 2 * (i ? pre[i - 1] : 0) + 2 * (i ? preSum[i - 1] : 0) + 2);
	}
	bw (i, r + 1, m + 1) {
		if (i < r) cuba[i] = max(cuba[i], cuba[i + 1]);
		cuba[i] = max(cuba[i], chL.query(i) + i * i + 3 * i + 2 * suf[i + 1] - 2 * preSum[i] + 2);
	}
	fw (i, l, r + 1) ans[i] = max(ans[i], cuba[i]);
	solve(l, m); solve(m + 1, r);
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fw (i, 0, n) cin >> a[i];
	fw (i, 0, n) preSum[i] = (i ? preSum[i - 1] : 0) + a[i];
	bw (i, n, 0) sufSum[i] = sufSum[i + 1] + a[i];
//	For each drink, find the cost if it is forced to be included in the list of drinks.
//	The task is find L and R that (R - L) * (R - L - 1) + 2 * (pre[L] + suf[R] + sum[R - 1] - sum[L]) is maximum
//	Build a convex hull of all L < i, then answering for R is querying for x = R.
	ch.init();
	ch.add_line(2, 2);
	//j = -1 for initial state.
	fw (i, 0, n) {
		pre[i] = ch.query(i);
		pre[i] += i * i + i - 2 * preSum[i];
		pre[i] = max(pre[i], i ? pre[i - 1] : 0);
		ch.add_line(-2 * i, pre[i] + i * i - i + 2 * preSum[i]);
	}
	
	ch.init();
	ch.add_line(-2 * n, n * n + n);
	//j = n for initial state
	suf[n] = 0;
	bw (i, n, 0) {
		suf[i] = ch.query(i);
		suf[i] += i * i - i - 2 * sufSum[i];
		suf[i] = max(suf[i], suf[i + 1]);
		ch.add_line(-2 * i, suf[i] + i * i + i + 2 * sufSum[i]);
	}
	fw (i, 0, n) pre[i] /= 2, suf[i] /= 2;
//	fw (i, 0, n) cout << pre[i] << " " << suf[i] << "\n";
	memset(ans, -63, sizeof ans);
	solve(0, n - 1);
	fw (i, 0, n) {
//		cout << "Ans[" << i << "] = " << ans[i] << "\n";
		assert(ans[i] % 2 == 0);
		ans[i] /= 2;
	}
//	fw (i, 0, n) cout << ans[i] << " "; cout << "\n";	
	cin >> m;
	while (m--) {
		int p, x;
		cin >> p >> x;
		p--;
		int ans1 = (p ? pre[p - 1] : 0) + suf[p + 1];
		int ans2 = ans[p] - x + a[p];
		cout << max(ans1, ans2) << "\n";
	}
	return 0;
}

Measured memory_bytes: 19072