#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
#define ll long long
int n,m,T[N],q[N];
ll Y[N],sum[N],fl[N],fr[N],f[N],tmp[N];
inline double slope(int x,int y){
	return 1.0*(Y[y]-Y[x])/(y-x);
}
inline void dp(ll *f){
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+T[i];
	int top=0;f[0]=0;q[++top]=0;
	for(int i=1;i<=n;++i){
		while(top>1 && slope(q[top-1],q[top])<=i) --top;
		f[i]=max(f[i-1],f[q[top]]+1ll*(i-q[top])*(i-q[top]+1)/2-(sum[i]-sum[q[top]]));
		Y[i]=f[i]+sum[i]+1ll*i*(i-1)/2;
		while(top>1 && slope(q[top-1],q[top])<=slope(q[top],i)) --top;
		q[++top]=i;
	}
}
void solve(ll *f1,ll *f2,int l,int r){
	if(l==r){
		f[l]=max(f[l],f1[l-1]+f2[l+1]-T[l]+1);
		return;
	}
	int mid=l+r>>1,top=0;
	for(int i=l-1;i<mid;++i){
		Y[i]=f1[i]+sum[i]+1ll*i*(i-1)/2;
		while(top>1 && slope(q[top-1],q[top])<=slope(q[top],i)) --top;
		q[++top]=i;
	}
	for(int i=mid;i<=r;++i){
		while(top>1 && slope(q[top-1],q[top])<=i) --top;
		tmp[i]=f1[q[top]]+f2[i+1]+1ll*(i-q[top])*(i-q[top]+1)/2-(sum[i]-sum[q[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(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&T[i]);
	dp(fl);reverse(T+1,T+n+1);dp(fr);
	reverse(T+1,T+n+1);reverse(fr+1,fr+n+1);
//	for(int i=1;i<=n;++i) printf("%d ",fl[i]);puts("");
//	for(int i=1;i<=n;++i) printf("%d ",fr[i]);puts("");
	for(int i=1;i<=n;++i) f[i]=-T[i],sum[i]=sum[i-1]+T[i];
	solve(fl,fr,1,n);
// for(int i=1;i<=n;++i) printf("%d ",f[i]);puts("");
	reverse(T+1,T+n+1);reverse(f+1,f+n+1);reverse(fl+1,fl+n+1);reverse(fr+1,fr+n+1);
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+T[i];
	solve(fr,fl,1,n);
	reverse(T+1,T+n+1);reverse(f+1,f+n+1);reverse(fl+1,fl+n+1);reverse(fr+1,fr+n+1);
// for(int i=1;i<=n;++i) printf("%d ",f[i]);puts("");
//	for(int i=1;i<=)
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		int x,y;scanf("%d%d",&x,&y);
		printf("%lld\n",max(fl[x-1]+fr[x+1],f[x]+T[x]-y));
	}
	return 0;
}