#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 300005;

int n, m, q[MAXN], t[MAXN];
LL s[MAXN], f[MAXN], g[MAXN], h[MAXN], y[MAXN], pre[MAXN], suf[MAXN], b[MAXN];

inline void Dp(LL *f)
{
	int r;
	q[r = 1] = 0;
	for (int i = 1; i <= n; i ++)
	{
		s[i] = s[i - 1] + t[i];
		while (r > 1 && y[q[r]] - y[q[r - 1]] <= 1LL * i * (q[r] - q[r - 1]))
			r --;
		f[i] = max(f[i - 1], f[q[r]] - s[i] + s[q[r]] + (1LL * (i - q[r]) * (i - q[r] + 1) >> 1));
		y[i] = f[i] + s[i] + (1LL * i * (i - 1) >> 1);
		while (r > 1 && (y[i] - y[q[r]]) * (q[r] - q[r - 1]) >= (y[q[r]] - y[q[r - 1]]) * (i - q[r]))
			r --;
		q[++ r] = i;
	}
}

inline void Solve(int l, int r, LL *pre, LL *suf, LL *f)
{
	if (l == r)
		return (void)(f[l] = 1LL - t[l]);
	int mid = l + r - 1 >> 1, c = 0;
	Solve(l, mid, pre, suf, f);
	Solve(mid + 1, r, pre, suf, f);
	for (int i = l - 1; i < mid; i ++)
	{
		y[i] = pre[i] + s[i] + (1LL * i * (i - 1) >> 1);
		while (c > 1 && (y[i] - y[q[c]]) * (q[c] - q[c - 1]) >= (y[q[c]] - y[q[c - 1]]) * (i - q[c]))
			c --;
		q[++ c] = i;
	}
	for (int i = mid + 1; i <= r; i ++)
	{
		while (c > 1 && y[q[c]] - y[q[c - 1]] <= 1LL * i * (q[c] - q[c - 1]))
			c --;
		b[i] = pre[q[c]] - s[i] + s[q[c]] + (1LL * (i - q[c]) * (i - q[c] + 1) >> 1) + suf[i + 1];
	}
	for (int i = r - 1; i > mid; i --)
		b[i] = max(b[i], b[i + 1]);
	for (int i = mid + 1; i <= r; i ++)
		f[i] = max(f[i], b[i]);
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		t[i] = Read();
	Dp(f);
	reverse(t + 1, t + n + 1);
	Dp(g);
	reverse(t + 1, t + n + 1);
	reverse(g + 1, g + n + 1);
	for (int i = 1; i <= n; i ++)
		s[i] = s[i - 1] + t[i];
	Solve(1, n, f, g, pre);
	reverse(t + 1, t + n + 1);
	reverse(f + 1, f + n + 1);
	reverse(g + 1, g + n + 1);
	for (int i = 1; i <= n; i ++)
		s[i] = s[i - 1] + t[i];
	Solve(1, n, g, f, suf);
	reverse(t + 1, t + n + 1);
	reverse(f + 1, f + n + 1);
	reverse(g + 1, g + n + 1);
	reverse(suf + 1, suf + n + 1);
	m = Read();
	while (m --)
	{
		int p = Read(), x = Read();
		printf("%lld\n", max(f[p - 1] + g[p + 1], max(pre[p], suf[p]) - x + t[p]));
	}
}
