#include <bits/stdc++.h>
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
#define clv(V) (V).clear()
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define upmax(a,b) (a)=max((a),(b))
using namespace std;
const db pi = acos(-1.0);
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

typedef long long ll;
typedef pair<ll, ll> pll;
ll operator * (pll a, pll b) { return a.X * b.Y - b.X * a.Y; }
ll ccw(pll a, pll b, pll c) { return a * b + b * c + c * a; }
struct Node
{
	vector<pll> V;
	void init() { clv(V); }
	void push(ll a, ll b)
	{
		for(; 1 < sz(V) && ccw(befv(V), V.back(), {a, b}) <= 0; V.pop_back());
		V.pb({a, b});
	}
	ll f(ll x, int idx) { return V[idx].X * x + V[idx].Y; }
	ll f(ll x)
	{
		if(V.empty()) return -INFLL;
		int s = 0, e = sz(V) - 1;
		for(int m; s < e;)
		{
			m = (s + e) / 2;
			ll l = f(x, m), r = f(x, m + 1);
			if(l < r) s = m + 1; 
			else e = m;
		}
		return f(x, s);
	}
};
const int Mn = 300010;
Node a;
ll L[Mn], R[Mn], P[Mn], S[Mn], T[Mn];
int N, M;

void f(ll d[]) 
{
	rep(i, 1, N) S[i] = S[i - 1] + T[i];
	a.init(); a.push(0, 0);
	rep(i, 1, N)
	{
		d[i] = max(d[i - 1], a.f(i) + ((ll)i * i + i) / 2 - S[i]);
		a.push(-i, d[i] + S[i] + ((ll)i * i - i) / 2);
	}
}

void f(ll d[], int s, int e) 
{
	if(s > e) return;
	if(s == e) 
	{
		upmax(d[s], L[s - 1] + R[s + 1] + 1 - T[s]);
		return;
	}
	int m = (s + e) / 2; ll x = -INFLL;
	a.init();
	rep(j, m + 1, e)
		a.push(-j, R[j + 1] - S[j] + ((ll)j * j + j) / 2);
	rep(i, s - 1, m - 1) 
	{
		ll t = a.f(i) + L[i] + S[i] + ((ll)i * i - i) / 2;
		upmax(x, t); 
		upmax(d[i + 1], x);
	}
	a.init(); 
	x = -INFLL;
	rep(i, s - 1, m - 1)
		a.push(-i, L[i] + S[i] + ((ll)i * i - i) / 2);
	for(int j = e; m < j; j --) 
	{
		ll t = a.f(j) + R[j + 1] - S[j] + ((ll)j * j + j) / 2;
		upmax(x, t); 
		upmax(d[j], x);
	}
	f(d, s, m); 
	f(d, m + 1, e);
}

int main()
{
	scanf("%d", &N);
	rep(i, 1, N) scanf("%lld", &T[i]);
	f(L); reverse(T + 1, T + N + 1);
	f(R); reverse(R + 1, R + N + 1);
	reverse(T + 1, T + N + 1);
	rep(i, 1, N) S[i] = S[i  -1] + T[i];
	fill(P + 1, P + N + 1, -INFLL);
	f(P, 1, N);
	M = read();
	while(M --)
	{
		int p = read();
		ll x;
		scanf("%lld", &x);
		printf("%lld\n", max(0ll, max(L[p - 1] + R[p + 1], P[p] + T[p] - x)));
	}
	return 0;
}
