// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 210000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
struct LiChaoTree{
	// Stack領域が小さいと壊れがちなので適宜調整してください
	// ulimit -s 65532
	typedef long long vint;
	typedef int zint;
	typedef pair<vint,vint> F;
	int seg_sz;
	static const vint inf=mod*mod;
	static const zint xinf=mod;
	vector<zint>x;
	vector<F>segtree;
	// F segtree[seg_sz*2];
	vint func(F a,zint x){
		return a.first*x+a.second;
	}
	void add_line(int a,int b,int c,F f){
		if(segtree[c]==make_pair((vint)0,inf)){
			segtree[c]=f;
			return;
		}
		int m=(a+b)/2;
		zint lx=x[a];
		zint mx=x[m];
		zint rx=x[b-1];
		vint ly1=func(segtree[c],lx);
		vint my1=func(segtree[c],mx);
		vint ry1=func(segtree[c],rx);
		vint ly2=func(f,lx);
		vint my2=func(f,mx);
		vint ry2=func(f,rx);
		if(ly1<=ly2&&ry1<=ry2){
			return;
		}
		if(ly1>ly2&&ry1>ry2){
			segtree[c]=f;
			return;
		}
		if(my1>my2){
			swap(segtree[c],f);
			if(ly1>ly2){
				add_line(m,b,c*2+1,f);
			}else{
				add_line(a,m,c*2,f);
			}
			return;
		}
		if(ly1>ly2){
			add_line(a,m,c*2,f);
		}else{
			add_line(m,b,c*2+1,f);
		}
	}
	void add_line(int a,int b,int c,int d,int e,F f){
		if(d<=a||b<=c)return;
		if(c<=a&&b<=d){
			add_line(a,b,e,f);
			return;
		}
		add_line(a,(a+b)/2,c,d,e*2,f);
		add_line((a+b)/2,b,c,d,e*2+1,f);
	}
	vint query(zint X){
		int zx=lower_bound(x.begin(),x.end(),X)-x.begin();
		zx+=seg_sz;
		vint ret=inf;
		while(zx){
			ret=min(ret,func(segtree[zx],X));
			zx/=2;
		}
		return ret;
	}

	void add_line(F a){
		add_line(0,seg_sz,1,a);
	}
	void add_line(F a,zint b,zint c){ // add [b,c)
		int l=lower_bound(x.begin(),x.end(),b)-x.begin();
		int r=lower_bound(x.begin(),x.end(),c)-x.begin();
		if(l>=r)return;
		add_line(0,seg_sz,l,r,1,a);
	}

	void init(vector<zint>X){
		// printf("sz: %d\n",(int)X.size());
		seg_sz=1;
		while(seg_sz<(int)X.size()){
			seg_sz*=2;
		}
		segtree=vector<F>(seg_sz*2);
		x=vector<zint>(seg_sz);
		for(int i=0;i<seg_sz*2;i++){
			segtree[i]=make_pair((vint)0,inf);
		}
		std::sort(X.begin(),X.end());
		for(int i=0;i<X.size();i++){
			x[i]=X[i];
		}
		for(int i=X.size();i<seg_sz;i++){
			x[i]=x[i-1];
		}
	}
};
long long p[310000];
pair<int,int>ev[310000];
long long dpL[310000];
long long dpR[310000];
long long ret[310000];
int q1[310000];
long long q2[310000];
int Q;int N;
void calc(int a,int b){
	if(a>=b)return;
	if(a+1==b){
		int lz=lower_bound(ev,ev+Q,make_pair(a,0))-ev;
		int rz=lower_bound(ev,ev+Q,make_pair(b,0))-ev;
		for(int i=lz;i<rz;i++){
			int I=ev[i].second;
			ret[I]=max(ret[I],1-q2[I]+1+dpL[a]+dpR[N-1-a]);
		}
		return;
	}
	int M=(a+b)/2;

	calc(a,M);
	calc(M,b);
	int lz=lower_bound(ev,ev+Q,make_pair(a,0))-ev;
	int mz=lower_bound(ev,ev+Q,make_pair(M,0))-ev;
	int rz=lower_bound(ev,ev+Q,make_pair(b,0))-ev;
	LiChaoTree left;
	LiChaoTree right;
	vector<int>X;
	for(int i=0;i<=M-a;i++)X.push_back(1+i);
	left.init(X);
	long long cs=0;
	for(int i=M;i<=b;i++){
		long long B=(long long)(i-M)*(i-M+1)/2;
		B+=dpR[N-i];
		B-=cs;
		left.add_line(make_pair(-(i-M),-B));
		if(i<b)cs+=p[i];
	}
	int at=lz;
	long long bes=-inf;
	long long ds=0;
	for(int i=a;i<M;i++)ds+=p[i];
	for(int i=a;i<M;i++){
		bes=max(bes,dpL[i]+(long long)(M-i)*(M-i+1)/2-ds-left.query(M-i));
		while(at<mz&&ev[at].first==i){
			int I=ev[at].second;
			ret[I]=max(ret[I],bes+p[i]-q2[I]);
			at++;
		}
		ds-=p[i];
	}
	X.clear();
	for(int i=0;i<=b-M;i++)X.push_back(1+i);
	right.init(X);
	cs=0;
	ds=0;
	bes=-inf;
	at=rz-1;
	for(int i=M;i>=a;i--){
		long long B=(long long)(M-i)*(M-i+1)/2;
		B+=dpL[i];
		B-=cs;
		right.add_line(make_pair(-(M-i),-B));
		if(i>a)cs+=p[i-1];
	}
	for(int i=M;i<b;i++)ds+=p[i];
	for(int i=b-1;i>=M;i--){
		bes=max(bes,dpR[N-1-i]+(long long)(i-M+1)*(i-M+2)/2-ds-right.query(i-M+1));
		while(at>=mz&&ev[at].first==i){
			int I=ev[at].second;
			ret[I]=max(ret[I],bes+p[i]-q2[I]);
			at--;
		}
		ds-=p[i];
	}
}
int main(){
	int a;scanf("%d",&a);N=a;
	for(int i=0;i<a;i++){
		scanf("%lld",p+i);
	}
	int b;scanf("%d",&b);Q=b;
	for(int i=0;i<b;i++){
		int s;
		long long t;
		scanf("%d%lld",&s,&t);s--;
		ev[i]=make_pair(s,i);
		q1[i]=s;
		q2[i]=t;
	}
	LiChaoTree left;
	LiChaoTree right;
	vector<int>X(a+1);
	for(int i=0;i<=a;i++){
		X[i]=i;
	}
	left.init(X);
	right.init(X);
	for(int i=0;i<a;i++){
		dpL[i+1]=dpL[i]+p[i];
		dpL[i+1]=max(dpL[i+1],(long long)(i+1)*i/2-left.query(i)+p[i]);
		 // printf("%lld %lld %lld\n",i,-dpL[i]-(long long)i*(i-1)/2,(long long)(i+1)*i/2);
		left.add_line(make_pair(i,-dpL[i]-(long long)i*(i-1)/2));
	}
	for(int i=0;i<a;i++){
		dpR[i+1]=dpR[i]+p[a-1-i];
		dpR[i+1]=max(dpR[i+1],(long long)(i+1)*i/2-right.query(i)+p[a-1-i]);
		right.add_line(make_pair(i,-dpR[i]-(long long)i*(i-1)/2));
	}
	long long cur=0;
	for(int i=0;i<a;i++){
		cur+=p[i];
		dpL[i+1]-=cur;
	}
	cur=0;
	for(int i=0;i<a;i++){
		cur+=p[a-1-i];
		dpR[i+1]-=cur;
	}
	// for(int i=0;i<=a;i++){
	// 	printf("%lld %lld\n",dpL[i],dpR[i]);
	// }
	for(int i=0;i<b;i++){
		ret[i]=dpL[q1[i]+1]+dpR[(a-1-q1[i])+1];
	}
	// for(int i=0;i<b;i++){
	// 	printf("%lld\n",ret[i]);
	// }
	std::sort(ev,ev+b);
	calc(0,a);
	for(int i=0;i<b;i++){
		printf("%lld\n",ret[i]);
	}
}


Measured memory_bytes: 73948