#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 300010
using namespace std;
typedef long long ll;
ll f[MAXN],f1[MAXN],f2[MAXN];
ll t[MAXN];
ll st[MAXN],q[MAXN];
ll sum[MAXN],tmp[MAXN];
int n,m;
void prepare(ll fx[]){
	fx[0]=0;
	int top=0;
	st[++top]=0;
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	for(ll i=1;i<=n;i++){
		fx[i]=fx[i-1];
		while(top>1&&q[st[top]]-q[st[top-1]]<=2ll*i*(st[top]-st[top-1]))
			top--;
		fx[i]=max(fx[i],fx[st[top]]+(i-st[top])*(i-st[top]+1)/2ll-sum[i]+sum[st[top]]);
		q[i]=i*i-i+2ll*(fx[i]+sum[i]);
		while(top>1&&(q[st[top]]-q[st[top-1]])*(i-st[top-1])<=(q[i]-q[st[top-1]])*(st[top]-st[top-1]))
			top--;
		st[++top]=i;
	}
}
void solve(ll f1[],ll f2[],ll l,ll r){
	if(l==r){
		f[l]=max(f[l],f1[l-1]+f2[l+1]-t[l]+1ll);
		return ;
	}
	int mid=(l+r)>>1,top=0;
	for(ll i=l-1;i<mid;i++){
		q[i]=i*i-i+2ll*(f1[i]+sum[i]);
		while(top>1&&(q[st[top]]-q[st[top-1]])*(i-st[top-1])<=(q[i]-q[st[top-1]])*(st[top]-st[top-1]))
			top--;
		st[++top]=i;
	}
	for(ll i=mid;i<=r;i++){
		while(top>1&&q[st[top]]-q[st[top-1]]<=2ll*i*(st[top]-st[top-1]))
			top--;
		tmp[i]=f1[st[top]]+f2[i+1]+(i-st[top])*(i-st[top]+1)/2ll-sum[i]+sum[st[top]];
	}
	for(int i=r-1;i>=mid;i--)
		tmp[i]=max(tmp[i],tmp[i+1]);
	for(int i=mid;i<=r;i++)
		f[i]=max(f[i],tmp[i]);
	solve(f1,f2,l,mid);
	solve(f1,f2,mid+1,r);
}
int main(){
	SF("%d",&n);
	for(int i=1;i<=n;i++){
		SF("%lld",&t[i]);
		f[i]=-t[i]+1ll;
	}
	prepare(f1);
	reverse(t+1,t+1+n);
	prepare(f2);
	reverse(t+1,t+1+n);
	reverse(f2+1,f2+1+n);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	solve(f1,f2,1,n);
	reverse(t+1,t+1+n);reverse(f1+1,f1+1+n),reverse(f2+1,f2+1+n);reverse(f+1,f+1+n);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	solve(f2,f1,1,n);
	reverse(t+1,t+1+n);reverse(f1+1,f1+1+n),reverse(f2+1,f2+1+n);reverse(f+1,f+1+n);
	SF("%d",&m);
	for(int i=1;i<=m;i++){
		int p;
		ll t1;
		SF("%d%lld",&p,&t1);
		PF("%lld\n",max(f1[p-1]+f2[p+1],f[p]+t[p]-t1));
	}
}