#include <bits/stdc++.h>

const int MAXN = 300010;
typedef long long LL;
const LL NINF = 0xcfcfcfcfcfcfcfcfLL;
int n, Q;
LL A[MAXN], L[MAXN], R[MAXN];
LL g[MAXN], pre[MAXN];
bool cmpat(int j, int k, LL x) {
	return g[j] - g[k] <= x * (j - k);
}
bool cmpsl(int i, int j, int k) {
	return (g[i] - g[j]) * (j - k) >= (g[j] - g[k]) * (i - j);
}
int st[MAXN], top;
void moveto(int x) {
	while (top > 1 && cmpat(st[top], st[top - 1], x)) --top;
}
void push(int i) {
	while (top > 1 && cmpsl(i, st[top], st[top - 1])) --top;
	st[++top] = i;
}
void solve(LL * A, LL * f) {
	st[top = 1] = 0;
	for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + A[i];
	for (int i = 1; i <= n; ++i) {
		moveto(i);
		int j = st[top];
		f[i] = f[j] + (i - j) * (i - j + 1ll) / 2 - pre[i] + pre[j];
		f[i] = std::max(f[i], f[i - 1]);
		g[i] = f[i] + pre[i] + i * (i - 1ll) / 2;
		push(i);
	}
}
LL ansl[MAXN], flg[MAXN];
inline int rx(int x, int l, int r) { return r - x + l; }
void solve(int l, int r) {
	if (l > r) return ;
	if (l == r) return (void) (ansl[l] = L[l - 1] + R[r + 1] - A[l] + 1);
	int mid = l + r >> 1;
	solve(l, mid); solve(mid + 1, r);
	pre[l - 1] = pre[r + 1] = 0; flg[l - 1] = flg[r + 1] = NINF;
	for (int i = l; i <= r; ++i) pre[i] = pre[i - 1] + A[i];
	top = 0;
	for (int i = l - 1; i <= mid; ++i) {
		g[i] = L[i] + pre[i] + i * (i - 1ll) / 2;
		push(i);
	}
	for (int i = mid + 1; i <= r; ++i) {
		moveto(i);
		int j = st[top];
		LL t = R[i + 1] + L[j];
		t += (i - j) * (i - j + 1ll) / 2 - pre[i] + pre[j];
		flg[i] = t;
	}
	for (int i = r; i > mid; --i)
		ansl[i] = std::max(ansl[i], flg[i] = std::max(flg[i], flg[i + 1]));
	top = 0;
	for (int i = l; i <= r; ++i) pre[i] = pre[i - 1] + A[rx(i, l, r)];
	for (int i = r + 1; i > mid; --i) {
		int j = rx(i, l, r);
		g[j] = R[i] + pre[j] + j * (j - 1ll) / 2;
		push(j);
	}
	for (int i = mid; i >= l; --i) {
		int j = rx(i, l, r);
		moveto(j);
		int k = st[top], nk = rx(k, l, r);
		LL t = L[i - 1] + R[nk];
		t += (j - k) * (j - k + 1) / 2 - pre[j] + pre[k];
		flg[i] = t;
	}
	for (int i = l; i <= mid; ++i)
		ansl[i] = std::max(ansl[i], flg[i] = std::max(flg[i], flg[i - 1]));
}
#define rev(X) std::reverse(X + 1, X + 1 + n)
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n;
	for (int i = 1; i <= n; ++i) std::cin >> A[i];
	solve(A, L); rev(A);
	solve(A, R); rev(A); rev(R);
	memset(ansl, 0xcf, sizeof ansl);
	solve(1, n);
	std::cin >> Q;
	while (Q --> 0) {
		int x, v; std::cin >> x >> v;
		LL ans = std::max(L[x - 1] + R[x + 1], ansl[x] + A[x] - v);
		std::cout << ans << std::endl;
	}
	return 0;
}
