#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=300000+19;
const ll oo=1ll<<60;

struct Point{
	ll x,y;
	ll At(ll w){
		return x*w+y;
	}
} stk[N];
typedef Point Vector;

Vector operator - (Point A,Point B) {return (Vector){A.x-B.x,A.y-B.y};}
db cross(Vector A,Vector B){
	return 1.0*A.x*B.y-1.0*A.y*B.x;
}

ll sl[N],sr[N],T[N],f[N],g[N],res[N],val[N];
int n,x,v,top,Qc;

struct QType{
	int v,id;
};vector<QType> V[N];

void Query(int i){
	while (top>=2){
		Point B=stk[top];
		Point A=stk[top-1];
		if (B.At(i)<=A.At(i)) top--;else break;
	}
}
void Insert(Point C){
	while (top>=2){
		Point B=stk[top];
		Point A=stk[top-1];
		if (cross(B-A,C-A)<=0) top--;else break;
	}
	stk[++top]=C;
}
void Work(int l,int r){
	if (l==r) return;
	int mid=((l+r)>>1);
	
	//[l,mid]->[mid+1,r]
	top=0;
	stk[++top]=(Point){0,0};
	For(i,l,mid+1){
		Insert((Point){-i,f[i]+(1ll*i*i-i)/2+sl[i]});
	}
	For(i,mid+1,r+1){
		Query(i);
		val[i]=stk[top].At(i)+(1ll*i*i+i)/2-sl[i];
	}
	ll mx=-oo;
	for (int i=r;i>mid;i--){
		mx=max(mx,val[i]+g[n-i]);
		for (QType Q:V[i]){
			res[Q.id]=max(res[Q.id],mx+T[i]-Q.v);
		}
	}
	
	//[l,mid]<-[mid+1,r]
	top=0;
	stk[++top]=(Point){0,0};
	for (int j=r,i;j>mid;j--){
		i=n-j+1;
		Insert((Point){-i,g[i]+(1ll*i*i-i)/2+sr[i]});
	}
	for (int j=mid,i;j>=l;j--){
		i=n-j+1;
		Query(i);
		val[j]=stk[top].At(i)+(1ll*i*i+i)/2-sr[i];
	}
	mx=-oo;
	for (int j=l;j<=mid;j++){
		mx=max(mx,val[j]+f[j-1]);
		for (QType Q:V[j]){
			res[Q.id]=max(res[Q.id],mx+T[j]-Q.v);
		}
	}

	Work(l,mid);
	Work(mid+1,r);
}
void calc(ll *res,ll *sum){
	top=0;
	stk[++top]=(Point){0,0};
	For(i,1,n+1){
		Query(i);
		res[i]=max(res[i-1],stk[top].At(i)+(1ll*i*i+i)/2-sum[i]);
		Insert((Point){-i,res[i]+(1ll*i*i-i)/2+sum[i]});
	}
}

int main(){
	n=IN();
	For(i,1,n+1) T[i]=IN();
	For(i,1,n+1){
		sl[i]=sl[i-1]+T[i];
		sr[i]=sr[i-1]+T[n-i+1];
	}
	calc(f,sl);
	calc(g,sr);
	Qc=IN();
	For(i,1,Qc+1){
		x=IN(),v=IN();
		V[x].pb((QType){v,i});
		res[i]=f[x-1]+g[n-x];
	}
	
	Work(1,n);
	
	For(i,1,Qc+1) printf("%lld\n",res[i]);
}