#include<bits/stdc++.h>
typedef long long i64;
const int N=3e5+7;
int n,m,v0[N],q[N];
i64 s[N],f0[N],f1[N],rs[N],tmp[N];
i64 max(i64 a,i64 b){return a>b?a:b;}
struct pos{
	i64 x,y;
	i64 operator*(const pos&w)const{return x*w.y-y*w.x;}
	pos operator-(const pos&w)const{return (pos){x-w.x,y-w.y};}
}ss[N],w;
int sp;
struct info{
	int v0[N];
	i64 s[N],f[N],mf[N],f1[N];
	pos ps[N];
	void push(int i){
		while(sp&&(ss[sp]-ss[sp-1])*(ps[i]-ss[sp-1])>=0)--sp;
		ss[++sp]=ps[i];
	}
	i64 val(int i){
		while(sp&&(ss[sp]-ss[sp-1])*w>=0)--sp;
		return w*ss[sp]+i64(i+1)*i/2-s[i];
	}
	void pre(){
		ss[sp=0]=(pos){0,0};
		for(int i=1;i<=n;++i){
			s[i]=s[i-1]+v0[i];
			w=(pos){1,i};
			mf[i]=max(f[i]=val(i),mf[i-1]);
			ps[i]=(pos){i,mf[i]+i64(i-1)*i/2+s[i]};
			push(i);
			f1[i]=-(1ll<<60);
		}
	}
	void dac(int L,int R){
		if(L==R)return;
		int M=(L+R)>>1;
		dac(L,M),dac(M+1,R);
		sp=0;
		for(int i=L;i<=M;++i)push(i);
		for(int i=M+1;i<=R;++i){
			w=(pos){1,i};
			tmp[i]=val(i)+rs[i+1];
		}
		for(int i=R-1;i>M;--i)tmp[i]=max(tmp[i],tmp[i+1]);
		for(int i=R;i>M;--i)f1[i]=max(f1[i],tmp[i]);
	}
}i0,i1;
int $(int x){return n+1-x;}
char buf[20000007],*ptr=buf,ob[10000007],*op=ob;
int _(){
	int x=0;
	while(*ptr<48)++ptr;
	while(*ptr>47)x=x*10+*ptr++-48;
	return x;
}
void pr(i64 x){
	int ss[25],sp=0;
	do ss[++sp]=x%10;while(x/=10);
	while(sp)*op++=ss[sp--]+48;
	*op++=10;
}
int main(){
	fread(buf,1,sizeof(buf),stdin);
	n=_();
	for(int i=1;i<=n;++i)v0[i]=_(),i0.v0[i]=i1.v0[n+1-i]=v0[i];
	i0.pre();
	i1.pre();
	for(int i=1;i<=n+1;++i)rs[i]=i1.mf[$(i)];
	i0.dac(0,n);
	for(int i=1;i<=n+1;++i)rs[i]=i0.mf[$(i)];
	i1.dac(0,n);
	for(int i=1;i<=n;++i){
		f0[i]=i0.mf[i-1]+i1.mf[$(i+1)];
		f1[i]=max(i0.f1[i],i1.f1[$(i)]);
	}
	for(m=_();m;--m){
		int x=_(),y=_();
		pr(max(f0[x],f1[x]-y+v0[x]));
	}
	fwrite(ob,1,op-ob,stdout);
	return 0;
}