#include <cstdio>
#include <algorithm>

using std::max;

const int MAXN=300011;

int N, M;
int A[MAXN];

long long V[MAXN], T[MAXN], Val[MAXN];
long long Pre[MAXN], Suf[MAXN];
long long F[MAXN], G[MAXN];

struct Pos{
	int x;
	long long y;
	Pos(){};
	Pos(int _x, long long _y){x=_x;y=_y;}
	long long v(int k){
		return 1LL*k*x+y;
	}
};

inline Pos operator - (const Pos &A, const Pos &B){
	return Pos(A.x-B.x, A.y-B.y);
}

inline long double operator * (const Pos &A, const Pos &B){
	return 1.0L*A.x*B.y-1.0L*B.x*A.y;
}

Pos St[MAXN];
int Top;

long long S_[MAXN], O_[MAXN];

void Push(Pos P){
	while(Top>1 && (St[Top]-St[Top-1])*(P-St[Top])>=0.0L)	--Top;
	St[++Top]=P;
}

long long Ask(int k){
	while(Top>1 && St[Top].v(k)<St[Top-1].v(k))	--Top;
	return St[Top].v(k);
}

long long OY(int p){
	return ((O_[p]+S_[p])<<1)+1LL*p*p-(long long)(p);
}

long long XO(long long v, int p){
	return ((v+1LL*p*p+(long long)(p))>>1)-S_[p];
}

void Calc(){
	Top=0;
	for(int i=1;i<=N;++i){
		Push(Pos(i-1, OY(i-1)));
		O_[i]=XO(Ask(-(i<<1)), i);
		O_[i]=max(O_[i], O_[i-1]);
	}
}


long long F_(int p){
	return ((F[p]+Pre[p])<<1)+1LL*p*p+(long long)(p);
}

long long G_(int p){
	return ((G[p]+Suf[p])<<1)+1LL*p*p-(long long)(p);
}

void Deal(int l, int r){
	if(l>r)	return;
	int m=(l+r)>>1;
	
	for(int i=m;i<=r;++i)	T[i]=0;
	Top=0;
	for(int i=l-1;i<=m-1;++i)	Push(Pos(i, F_(i)));
	for(int i=m+1;i<=r+1;++i)	T[i-1]=max(T[i-1], Ask(-(i<<1))+G_(i));
	for(int i=r-1;i>=m;--i)	T[i]=max(T[i], T[i+1]);
	for(int i=m;i<=r;++i)	V[i]=max(V[i], T[i]);
	
	for(int i=l;i<=m;++i)	T[i]=0;
	Top=0;
	for(int i=m+1;i<=r+1;++i)	Push(Pos(i, G_(i)));
	for(int i=l-1;i<=m-1;++i)	T[i+1]=max(T[i+1], Ask(-(i<<1))+F_(i));
	for(int i=l+1;i<=m;++i)	T[i]=max(T[i], T[i-1]);
	for(int i=l;i<=m;++i)	V[i]=max(V[i], T[i]);
	
	Deal(l, m-1);Deal(m+1, r);
}

void Show(long long v){
	printf("%lld\n", v);
}

int main(){
	
	scanf("%d", &N);
	for(int i=1;i<=N;++i)	scanf("%d", &A[i]);
	
	for(int i=1;i<=N;++i)	Pre[i]=Pre[i-1]+(long long)(A[i]);
	for(int i=N;i>=1;--i)	Suf[i]=Suf[i+1]+(long long)(A[i]);
	
	for(int i=1;i<=N;++i)
		S_[i]=Pre[i];
	Calc();
	for(int i=1;i<=N;++i)	F[i]=O_[i];
	
	for(int i=1;i<=N;++i)
		S_[N-i+1]=Suf[i];
	Calc();
	for(int i=1;i<=N;++i)	G[i]=O_[N-i+1];
	
	//for(int i=1;i<=N;++i)	printf("%I64d ", F[i]);
	//puts("");
	
	//for(int i=1;i<=N;++i)	printf("%I64d ", G[i]);
	//puts("");
	
	Deal(1, N);
	
	for(int i=1;i<=N;++i)	Val[i]=F[i-1]+G[i+1];
	for(int i=1;i<=N;++i)	V[i]=(V[i]>>1)-Pre[N];
	
	
	scanf("%d", &M);
	
	for(int p, x;M--;){
		scanf("%d%d", &p, &x);
		x=x-A[p];
		Show(max(Val[p], V[p]-x));
	}
	
	return 0;
}

/*
5
1 1 4 1 1

*/