#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=300000+10;
const ll inf=1000000000000000000;
ll sum[maxn],f[maxn],g[maxn],h[maxn],L[maxn],R[maxn],ans[maxn];
int dl[maxn],xy[maxn];
int i,j,k,l,r,t,n,m,head,tail;
ll num;
void revsum(){
	fd(i,n,1) sum[i]-=sum[i-1];
	reverse(sum+1,sum+n+1);
	fo(i,1,n) sum[i]+=sum[i-1];
}
void revLR(){
	fo(i,0,n+1) swap(L[i],R[n+1-i]);
}
ll S(int x){
	return (ll)x*(x+1)/2;
}
int getxy(int x,int y){
	/*int l=y+1,r=n+1,mid;
	while (l<r){
		mid=(l+r)/2;
		if (f[x]-sum[x]+S(mid-x)>=f[y]-sum[y]+S(mid-y)) r=mid;else l=mid+1;
	}
	return l;*/
	ll xx=f[x]-sum[x]+(ll)x*(x-1)/2;
	ll yy=f[y]-sum[y]+(ll)y*(y-1)/2;
	return int(max(min((yy-xx)%(y-x)==0?(yy-xx)/(y-x):(yy-xx)/(y-x)+1,(ll)n+1),(ll)y+1));
}
int getbest(int id){
	while (head<tail&&xy[tail-1]<=id) tail--;
	return dl[tail];
}
void put(int id){
	while (head<tail&&xy[tail-1]<=getxy(dl[tail],id)) tail--;
	dl[++tail]=id;
	if (head<tail) xy[tail-1]=getxy(dl[tail-1],id);
}
void dp(){
	f[0]=0;
	head=1;
	dl[tail=1]=0;
	fo(i,1,n){
		j=getbest(i);
		f[i]=f[j]+S(i-j)+sum[i]-sum[j];
		f[i]=max(f[i],f[i-1]);
		put(i);
	}
}
void solve(int l,int r,int c){
	if (l==r){
		g[l]=max(g[l],sum[l]-sum[l-1]+L[l-1]+R[l+1]+1);
		return;
	}
	int mid=(l+r+c)/2;
	int i,j,k;
	head=1;tail=0;
	fo(i,l-1,mid-1){
		f[i]=L[i];
		put(i);
	}
	fo(i,mid+1,r){
		j=getbest(i);
		h[i]=f[j]+S(i-j)+sum[i]-sum[j]+R[i+1];
	}
	fd(i,r-1,mid+1) h[i]=max(h[i],h[i+1]);
	fo(i,mid+1,r) g[i]=max(g[i],h[i]);
	solve(l,mid,c);solve(mid+1,r,c);
}
int main(){
	//freopen("genocide.in","r",stdin);freopen("genocide.out","w",stdout);
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%d",&t);
		t*=-1;
		sum[i]=sum[i-1]+(ll)t;
	}
	dp();
	fo(i,0,n) L[i]=f[i];
	revsum();
	dp();
	fo(i,0,n) R[n+1-i]=f[i];
	revsum();
	fo(i,1,n) g[i]=-inf;
	solve(1,n,0);
	fo(i,1,n) ans[i]=g[i];
	revsum();
	revLR();
	fo(i,1,n) g[i]=-inf;
	solve(1,n,-1);
	fo(i,1,n) ans[i]=max(ans[i],g[n-i+1]);
	revsum();
	revLR();
	fd(i,n,1) sum[i]-=sum[i-1];
	scanf("%d",&m);
	while (m--){
		scanf("%d%d",&j,&t);
		t*=-1;
		num=max(L[j-1]+R[j+1],ans[j]+t-sum[j]);
		printf("%lld\n",num);
	}
}