#include <algorithm>
#include <cstring>
#include <cstdio>
typedef long long ll;
int val[300005], que[300005];
ll sum[300005], dp_l[300005], dp_r[300005];
inline ll calc(ll *dp, int x, int y)
{
	ll a = dp[x] + (ll)x * (x - 1) / 2 - sum[x], b = dp[y] + (ll)y * (y - 1) / 2 - sum[y];
	return (b - a - 1) / (y - x) + 1;
}
inline void init(ll *dp, int n)
{
	int he = 0, ta = 0;
	for (int i = 1; i <= n; i++)
	{
		while (he < ta && calc(dp, que[ta - 1], que[ta]) <= i)
			ta--;
		int pos = que[ta];
		dp[i] = dp[pos] + (ll)(i - pos) * (i - pos + 1) / 2 + sum[i] - sum[pos];
		dp[i] = std::max(dp[i], dp[i - 1]);
		while (he < ta && calc(dp, que[ta - 1], que[ta]) <= calc(dp, que[ta], i))
			ta--;
		que[++ta] = i;
	}
}
ll dp[300005], ans[300005];
void work(int l, int r, int off)
{
	static ll tmp[300005];
	if (l == r)
	{
		dp[l] = std::max(dp[l], -val[l] + 1 + dp_l[l - 1] + dp_r[l + 1]);
		return;
	}
	int m = l + r + off >> 1, he = 0, ta = -1;
	for (int i = l - 1; i < m; i++)
	{
		while (he < ta && calc(dp_l, que[ta - 1], que[ta]) <= calc(dp_l, que[ta], i))
			ta--;
		que[++ta] = i;
	}
	for (int i = m + 1; i <= r; i++)
	{
		while (he < ta && calc(dp_l, que[ta - 1], que[ta]) <= i)
			ta--;
		int pos = que[ta];
		tmp[i] = dp_l[pos] + (ll)(i - pos) * (i - pos + 1) / 2 + sum[i] - sum[pos] + dp_r[i + 1];
	}
	for (int i = r; i > m; i--)
	{
		if (i != r)
			tmp[i] = std::max(tmp[i], tmp[i + 1]);
		dp[i] = std::max(dp[i], tmp[i]);
	}
	work(l, m, off);
	work(m + 1, r, off);
}
inline void rev(int n)
{
	std::reverse(val + 1, val + n + 1);
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] - val[i];
}
int main()
{
	// freopen("ARC066-F.in", "r", stdin);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", val + i);
		sum[i] = sum[i - 1] - val[i];
	}
	init(dp_l, n);
	rev(n);
	init(dp_r, n);
	std::reverse(dp_r + 1, dp_r + n + 1);
	rev(n);
	memset(dp, -0x3f, sizeof(dp));
	work(1, n, 0);
	memcpy(ans, dp, sizeof(dp));
	rev(n);
	for (int i = 1; i <= n; i++)
		std::swap(dp_l[i], dp_r[n - i + 1]);
	memset(dp, -0x3f, sizeof(dp));
	work(1, n, -1);
	for (int i = 1; i <= n; i++)
		ans[i] = std::max(ans[i], dp[n - i + 1]);
	rev(n);
	for (int i = 1; i <= n; i++)
		std::swap(dp_l[i], dp_r[n - i + 1]);
	int q;
	scanf("%d", &q);
	while (q--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%lld\n", std::max(dp_l[x - 1] + dp_r[x + 1], ans[x] + val[x] - y));
	}
	return 0;
}
