#include<bits/stdc++.h>
#define maxn 301000
using namespace std;
typedef long long ll;
ll s[maxn],ls[maxn],t[maxn],a[maxn],dpl[maxn],dpr[maxn],f[maxn];
int m,n,sta[maxn],tp;
ll cal(ll*dp,int i,int j){return -1ll*i*j+a[j];}
void pre(ll* dp){
	tp=0;
	sta[++tp]=0;
	for(int i=1;i<=n;++i){
		s[i]=s[i-1]+t[i];
		while(tp>1&&cal(dp,i,sta[tp])<cal(dp,i,sta[tp-1]))tp--;
		dp[i]=max(cal(dp,i,sta[tp])-s[i]+1ll*i*(i+1)/2,dp[i-1]),a[i]=1ll*i*(i-1)/2+s[i]+dp[i];
		while(tp>1&&1ll*(i-sta[tp-1])*(a[sta[tp]]-a[sta[tp-1]])<=1ll*(sta[tp]-sta[tp-1])*(a[i]-a[sta[tp-1]]))tp--;
		sta[++tp]=i;
	}
}
void solve(int l,int r,int ty){
	if(l==r){
		f[l]=max(f[l],dpl[l-1]+dpr[l+1]+1-t[l]);
		return ;
	}
	int mid=l+r-ty>>1,tp=0;
	solve(l,mid,ty),solve(mid+1,r,ty);
	for(int i=l-1;i<=mid;++i){
		a[i]=1ll*i*(i-1)/2+s[i]+dpl[i];
		while(tp>1&&1ll*(i-sta[tp-1])*(a[sta[tp]]-a[sta[tp-1]])<=1ll*(sta[tp]-sta[tp-1])*(a[i]-a[sta[tp-1]]))tp--;
		sta[++tp]=i;
	}
	ll mx=0;
	/*
	int lp=1;
	for(int i=r;i>=mid+1;--i){
		while(lp<tp&&cal(dpl,i,sta[lp])<cal(dpl,i,sta[lp+1]))lp++;
		mx=max(mx,dpr[i+1]+cal(dpl,i,sta[lp])+1ll*i*(i+1)/2-s[i]);
		f[i]=max(f[i],mx);
	}*/
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&cal(dpl,i,sta[tp])<cal(dpl,i,sta[tp-1]))tp--;
		ls[i]=dpr[i+1]+cal(dpl,i,sta[tp])+1ll*i*(i+1)/2-s[i];
	}
	for(int i=r;i>=mid+1;--i){
		if(i!=r)ls[i]=max(ls[i],ls[i+1]);
		f[i]=max(f[i],ls[i]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",&t[i]),f[i]=-1ll<<60;
	pre(dpl),reverse(t+1,t+n+1);
	pre(dpr),reverse(t+1,t+n+1),reverse(dpr+1,dpr+n+1);
	for(int i=1;i<=n;++i)s[i]=s[i-1]+t[i];
	solve(1,n,0),reverse(f+1,f+n+1);
	reverse(t+1,t+n+1),reverse(dpl+1,dpl+n+1);
	reverse(dpr+1,dpr+n+1),swap(dpl,dpr);
	for(int i=1;i<=n;++i)s[i]=s[i-1]+t[i];
	solve(1,n,1),reverse(f+1,f+n+1);
	reverse(t+1,t+n+1),reverse(dpl+1,dpl+n+1);
	reverse(dpr+1,dpr+n+1),swap(dpl,dpr);
	scanf("%d",&m);
	for(int i=1,p,nx;i<=m;++i)
		scanf("%d%d",&p,&nx),printf("%lld\n",max(dpl[p-1]+dpr[p+1],f[p]-nx+t[p]));
}