
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long int LL;
const int Max_N(300050);
const LL INF(0X3F3F3F3F3F3F3F3FLL);

template<typename Type>
void Get_Val(Type &Ret)
{
	Ret = 0;
	char ch;
	while (ch = getchar(), ch > '9' || ch < '0')
		;
	do
	{
		(Ret *= 10) += ch - '0';
	}
	while (ch = getchar(), ch >= '0' && ch <= '9');
}

int N;
LL T[Max_N], Pre[Max_N], L[Max_N], R[Max_N], G[Max_N];

struct node
{
	node(const LL &_x = 0LL, const LL &_y = 0LL) : x(_x), y(_y) {}
	LL x, y;
};
int FT, ED;
node Q[Max_N];

inline bool check(const node &a, const node &b, const node &c)
{
	return (a.y - b.y) * (b.x - c.x) > (b.y - c.y) * (a.x - b.x);
}

inline LL get(LL F[Max_N], LL j)
{
	return F[j] - Pre[j] + (j * j - j) / 2LL;
}

void getPre()
{
	for (int i = 1;i <= N;++i)
		Pre[i] = Pre[i - 1] - T[i];
}

void dp(LL F[Max_N])
{
	getPre();
	Q[FT = ED = 1] = node(0LL, get(F, 0LL));
	for (int i = 1, l, r, mid;i <= N;++i)
	{
		l = FT, r = ED;
		while (l < r)
		{
			mid = l + ((r - l) >> 1);
			if (mid + 1 > ED || Q[mid].y - i * Q[mid].x > Q[mid + 1].y - i * Q[mid + 1].x)
				r = mid;
			else
				l = mid + 1;
		}
		F[i] = max(F[i - 1], Q[l].y - i * Q[l].x + Pre[i] + (i * 1LL * i + i) / 2LL);
		while (FT + 1 <= ED && check(Q[ED - 1], Q[ED], node(i * 1LL, get(F, i * 1LL))) == false)
			--ED;
		Q[++ED] = node(i * 1LL, get(F, i * 1LL));
	}
}

inline LL get(LL i)
{
	return R[i + 1] + Pre[i] + (i * i + i) / 2LL;
}

LL Val[Max_N];
void cdq(int l, int r)
{
	if (l == r)
		return;
	int mid = l + ((r - l) >> 1);
	Q[FT = ED = 1] = node(l * 1LL, get(L, l * 1LL));
	for (int i = l + 1;i <= mid;++i)
	{
		while (FT + 1 <= ED && check(Q[ED - 1], Q[ED], node(i * 1LL, get(L, i * 1LL))) == false)
			--ED;
		Q[++ED] = node(i * 1LL, get(L, i * 1LL));
	}
	Val[r + 1] = -INF;
	for (int i = mid + 1;i <= r;++i)
	{
		while (FT + 1 <= ED && Q[ED].y - i * Q[ED].x < Q[ED - 1].y - i * Q[ED - 1].x)
			--ED;
		Val[i] = Q[ED].y - i * Q[ED].x + Pre[i] + (i * 1LL * i + i) / 2LL + R[i + 1];
	}
	for (int i = r;i >= mid + 1;--i)
		G[i] = max(G[i], Val[i] = max(Val[i], Val[i + 1]));
	Q[FT = ED = 1] = node(mid + 1LL, get(mid + 1LL));
	for (int i = mid + 2;i <= r;++i)
	{
		while (FT + 1 <= ED && check(Q[ED - 1], Q[ED], node(i * 1LL, get(i * 1LL))) == false)
			--ED;
		Q[++ED] = node(i * 1LL, get(i * 1LL));
	}
	Val[0] = -INF;
	for (int i = l;i <= mid;++i)
	{
		G[i] = max(G[i], Val[0]);
		while (FT + 1 <= ED && Q[ED].y - i * Q[ED].x < Q[ED - 1].y - i * Q[ED - 1].x)
			--ED;
		Val[0] = max(Val[0], Q[ED].y - i * Q[ED].x - Pre[i] + (i * 1LL * i - i) / 2LL + L[i]);
	}
	cdq(l, mid), cdq(mid + 1, r);
}

int main()
{
	Get_Val(N);
	for (int i = 1;i <= N;++i)
		Get_Val(T[i]);
	dp(L);
	reverse(T + 1, T + 1 + N), dp(R), reverse(R + 1, R + 1 + N);
	reverse(T + 1, T + 1 + N), getPre(), memset(G, -0X3F, sizeof(G)), cdq(0, N);
	int M;
	Get_Val(M);
	for (int p, x;M--;)
		Get_Val(p), Get_Val(x), printf("%lld\n", max(L[p - 1] + R[p + 1], G[p] + T[p] - x));
	return 0;
}