// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=300005;



long long N,T[MAXN];

long long q[MAXN],head,tail;

long long sum[MAXN],y[MAXN];

long long L[MAXN],R[MAXN],f[MAXN],g[MAXN],h[MAXN];



void DP(long long dp[],long long N)

{

	q[head=tail=1]=0;

	y[0]=0;

	for(long long i=1;i<=N;i++)

	{

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail];

			if((y[b]-y[a])<1LL*i*(b-a))

				tail--;

			else

				break;

		}

		long long j=q[tail];

		dp[i]=max(dp[i-1],dp[j]+(i-j)*(i-j-1)/2+(i-j)-sum[i]+sum[j]);

		y[i]=dp[i]+1LL*(i-1)*i/2+sum[i];

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail],c=i;

			if((y[b]-y[a])*(c-b)<1LL*(y[c]-y[b])*(b-a))

				tail--;

			else

				break;

		}

		q[++tail]=i;

	}

}



void CDQ(long long l,long long r,long long mode)

{

	if(l==r)

	{

		f[l]=max(f[l],L[l-1]+R[r+1]+1-T[l]);

		return;

	}

	long long mid=(l+r+mode)/2;

	CDQ(l,mid,mode);

	CDQ(mid+1,r,mode);

	

	q[head=tail=1]=l-1;

	g[l-1]=L[l-1];

	y[l-1]=g[l-1]+(l-1-1)*(l-1)/2+sum[l-1];

	for(long long i=l;i<=mid;i++)

	{

		g[i]=L[i];

		y[i]=g[i]+1LL*(i-1)*i/2+sum[i];

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail],c=i;

			if((y[b]-y[a])*(c-b)<1LL*(y[c]-y[b])*(b-a))

				tail--;

			else

				break;

		}

		q[++tail]=i;

	}

	

	for(long long i=mid+1;i<=r;i++)

	{

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail];

			if((y[b]-y[a])<1LL*i*(b-a))

				tail--;

			else

				break;

		}

		long long j=q[tail];

		g[i]=g[j]+(i-j)*(i-j-1)/2+(i-j)-sum[i]+sum[j]+R[i+1];

	}

	

	for(long long i=r-1;i>mid;i--)

		g[i]=max(g[i],g[i+1]);

	for(long long i=mid+1;i<=r;i++)

		f[i]=max(f[i],g[i]);

}



int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	

	scanf("%lld",&N);

	for(long long i=1;i<=N;i++)

		scanf("%lld",&T[i]);

	

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	DP(L,N);

	reverse(T+1,T+N+1);

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	DP(R,N);

	reverse(R+1,R+N+1);



	memset(h,0x80,sizeof h);

	

	for(long long i=1;i<=N;i++)

		swap(L[i],R[N-i+1]);

	

	memset(f,0x80,sizeof f);

	CDQ(1,N,-1);

	for(long long i=1;i<=N;i++)

		h[i]=max(h[i],f[N-i+1]);



	reverse(T+1,T+N+1);

	for(long long i=1;i<=N;i++)

		swap(L[i],R[N-i+1]);

	

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	

	memset(f,0x80,sizeof f);

	CDQ(1,N,0);

	for(long long i=1;i<=N;i++)

		h[i]=max(h[i],f[i]);

	

	long long M,P,X;

	scanf("%lld",&M);

	while(M--)

	{

		scanf("%lld%lld",&P,&X);

		long long ans=max(L[P-1]+R[P+1],h[P]+T[P]-X);

		printf("%lld\n",ans);

	}

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.827204340741233x):
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL sum[300003], pref[300003], suff[300003];

int t[300003];



bool Q;

struct Line {

    mutable LL k, m, p;

    bool operator<(const Line& o) const {

        return Q ? p < o.p : k < o.k;

    }

};

 

struct LineContainer : multiset<Line> {

    const LL inf = LLONG_MAX;

    void init(){

        clear();

    }

    LL div(LL a, LL b) {

        return a / b - ((a ^ b) < 0 && a % b);

    }

    bool isect(iterator x, iterator y) {

        if (y == end()) { x->p = inf; return false; }

        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;

        else x->p = div(y->m - x->m, x->k - y->k);

        return x->p >= y->p;

    }

    void add(LL k, LL m) {

        auto z = insert({k, m, 0}), y = z++, x = y;

        while (isect(y, z)) z = erase(z);

        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));

        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));

    }

    LL query(LL x) {

        if(empty()) return -1e18;

        Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;

        if(l.k*1.0*x + l.m >= 1e18) return 1e18;

        return l.k * x + l.m;

    }

}dpL, dpR;



int n, m;

LL dp[300003];

void dfs(int s, int e){

    int mid = (s+e)/2;



    LL res = 1 - t[mid];

    if(mid != 1) res += pref[mid-2];

    if(mid != n) res += suff[mid+2];

    dp[mid] = max(dp[mid], res);



    if(s >= e) return;



    dfs(s, mid);

    dfs(mid+1, e);



    dpL.init();

    dpR.init();

    for(int i=s;i<=mid;i++){

        LL m = -2*i, b = +2*sum[i-1] + i*1ll*i - 3*i + 2;

        if(i != 1) b += 2*pref[i-2];

        dpL.add(m, b);

    }

    for(int i=mid+1;i<=e;i++){

        LL m = -2*(n-i+1), b = +2*(sum[n] - sum[i]) + (n-i+1)*1ll*(n-i+1) - 3*(n-i+1) + 2;

        if(i != n) b += 2*suff[i+2];

        dpR.add(m, b);

    }



    LL mx = -1e18;

    for(int i=s;i<=mid;i++){

        LL res = (dpR.query(n-i+1) - 2*(sum[n] - sum[i-1]) + (n-i+1)*1ll*(n-i+1) + 3*(n-i+1))/2;

        if(i != n) res += pref[i-2];

        mx = max(mx, res);

        dp[i] = max(dp[i], mx);

    }



    mx = -1e18;

    for(int i=e;i>=mid+1;i--){

        LL res = (dpL.query(i) - 2*sum[i] + i*1ll*i + 3*i)/2;

        if(i != n) res += suff[i+2];

        mx = max(mx, res);

        dp[i] = max(dp[i], mx);

    }

}



int main(){

    scanf("%d", &n);   

    for(int i=1;i<=n;i++) scanf("%d", &t[i]), sum[i] = sum[i-1] + t[i], dp[i] = -1e18;



    for(int i=1;i<=n;i++){

        if(i != 1) pref[i] = pref[i-2] + 1 - t[i];

        else pref[i] = 1 - t[i];

        pref[i] = max(pref[i], (dpL.query(i) - 2*sum[i] + i*1ll*i + 3*i)/2);

        pref[i] = max(pref[i], pref[i-1]);

        LL m = -2*i, b = +2*sum[i-1] + i*1ll*i - 3*i + 2;

        if(i != 1) b += 2*pref[i-2];

        dpL.add(m, b);

    }



    for(int i=n;i>=1;i--){

        if(i != n) suff[i] = suff[i+2] + 1 - t[i];

        else suff[i] = 1 - t[i];

        suff[i] = max(suff[i], (dpR.query(n-i+1) - 2*(sum[n] - sum[i-1]) + (n-i+1)*1ll*(n-i+1) + 3*(n-i+1))/2);

        suff[i] = max(suff[i], suff[i+1]);

        LL m = -2*(n-i+1), b = +2*(sum[n] - sum[i]) + (n-i+1)*1ll*(n-i+1) - 3*(n-i+1) + 2;

        if(i != n) b += 2*suff[i+2];

        dpR.add(m, b);

    }

    dfs(1, n);

    scanf("%d", &m);

    for(int i=1;i<=m;i++){

        int p, x;

        scanf("%d%d", &p, &x);

        printf("%lld\n", max(dp[p] + t[p] - x, pref[p-1] + suff[p+1]));

    }

}