#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
struct Point{
	int x;
	long long y;
	inline Point operator -(const Point &P) const {
		return (Point){x - P.x, y - P.y};
	}
	inline long long operator *(const Point &P) const {
		return x * P.y - y * P.x;
	}
	inline long long operator ()(const int &z) const {
		return y - 1ll * x * z;
	}
}newp;
#define Calc(_A, _B, _C) ((_B - _A) * (_C - _A))
struct Hull{
	int siz;
	Point p[300006];
	void Clear() {
		siz = 0;
		return ;
	}
	void Safe_Clear() {
		while (siz) {
			p[siz].x = 0;
			p[siz].y = 0;
			--siz;
		}
		return ;
	}
	void Insert(const Point &P) {
		while (siz > 1 && Calc(p[siz - 1], p[siz], P) >= 0) --siz;
		p[++siz] = P;
		return ;
	}
	long long Query(const int &x) {
		while (siz > 1 && p[siz](x) < p[siz - 1](x)) --siz;
		//fprintf(stderr, "%d\n", p[siz].x);
		return p[siz](x);
	}
}q;
long long f[300006], g[300006], h[300006], b[300006], pre[300006], suf[300006], t[300006];
const long long NE = -0x3f3f3f3f3f3f3f3fll;	//NEgative Inf
void dq(register int l, register int r){
	if (l + 1 >= r) return ;
	register int i, mid = l + r >> 1;
	register long long tmp, now;
	q.Clear();
	newp.x = 0;
	newp.y = 0;
	q.Insert(newp);
	for (i = l; i < mid; ++i) {
		newp.x = i;
		newp.y = f[i] + (1ll * i * (i - 1) >> 1) + pre[i];
		q.Insert(newp);
	}
	for (i = mid; i < r; ++i) b[i] = q.Query(i) + (1ll * i * (i + 1) >> 1) - pre[i] + g[i + 1];
	now = NE;
	for (--i; i >= mid; --i) {
		cmax(now, b[i]);
		cmax(h[i], now);
	}
	q.Clear();
	for (i = r; i > mid; --i) {
		newp.x = -i;
		newp.y = g[i] + (1ll * i * (i + 1) >> 1) + suf[i];
		q.Insert(newp);
	}
	for (i = mid; i > l; --i) b[i] = q.Query(-i) + (1ll * i * (i - 1) >> 1) - suf[i] + f[i - 1];
	now = NE;
	for (++i; i <= mid; ++i) {
		cmax(now, b[i]);
		cmax(h[i], now);
	}
	dq(l, mid);
	dq(mid, r);
	return ;
}
int fastin(){
	register int i; register char ch;
	while (ch = getchar(), ch < '0' || ch > '9');
	i = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9') i = i * 10 + ch - '0';
	return i;
}
int main(){
	register int n, m, i, p, x;
	n = fastin();
	for (i = 1; i <= n; ++i) t[i] = fastin();
	for (i = 1; i <= n; ++i) pre[i] = pre[i - 1] + t[i];
	for (i = n; i; --i) suf[i] = suf[i + 1] + t[i];
	q.Clear();
	newp.x = 0;
	newp.y = 0;
	q.Insert(newp);
	for (i = 1; i <= n; ++i) {
		f[i] = q.Query(i) + (1ll * i * (i + 1) >> 1) - pre[i];
		cmax(f[i], f[i - 1]);
		newp.x = i;
		newp.y = f[i] + (1ll * i * (i - 1) >> 1) + pre[i];
		q.Insert(newp);
		//fprintf(stderr, "%d %lld\n", i, f[i]);
	}
	q.Clear();
	newp.x =  - n - 1;
	newp.y = 1ll * (n + 1) * (n + 2) >> 1;
	q.Insert(newp);
	for (i = n; i; --i) {
		g[i] = q.Query(-i) + (1ll * i * (i - 1) >> 1) - suf[i];
		cmax(g[i], g[i + 1]);
		newp.x = -i;
		newp.y = g[i] + (1ll * i * (i + 1) >> 1) + suf[i];
		q.Insert(newp);
	}
	for (i = 1; i <= n; ++i) h[i] = f[i - 1] + g[i + 1] + 1 - t[i];
	dq(0, n + 1);
	//for (i = 1; i <= n; ++i) fprintf(stderr, "%lld %lld %lld\n", f[i], g[i], h[i]);
	
	m = fastin();
	for (i = 1; i <= m; ++i) {
		p = fastin();
		x = fastin();
		printf("%lld\n", dmax(h[p] + t[p] - x, f[p - 1] + g[p + 1]));
	}
	return 0;
}

Measured memory_bytes: 20864