#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N,M;
lld a[300002],sum[300002],tmp[300002];
lld d[300002],d1[300002],d2[300002];
struct data{
	lld a,b;
	data(){}
	data(lld a,lld b):a(a),b(b){}
};
struct CHT{
	int cr,cf;
	data line[300002];
	void init(){
		cr = cf = -1;
	}
	lld ccw(data x,data y,data z){
		return (x.a*y.b+y.a*z.b+z.a*x.b)-(x.b*y.a+y.b*z.a+z.b*x.a);
	}
	lld f(int num,lld x){
		return line[num].a*x+line[num].b;
	}
	lld getv(lld x){
		while(cf && f(cf-1,x) >= f(cf,x)) cf--;
		return f(cf,x);
	}
	void add(lld a,lld b){
		while(cr > 0 && ccw(line[cr-1],line[cr],data(a,b)) <= 0) cr--;
		cf = min(cf,cr);
		if(cr != cf) return;
		cr++; cf++;
		line[cr] = {a,b};
	}
}cht;

void setting(lld D[]){
	cht.init();
	for(int i=1; i<=N; i++) sum[i] = sum[i-1]+a[i];
	cht.add(0,0);
	for(lld i=1; i<=N; i++){
		D[i] = max(cht.getv(i)+(i*(i+1)/2)-sum[i],D[i-1]);
		cht.add(-i,D[i]+sum[i]+(i*(i-1)/2));
	}
}

void divide(int s,int e){
	if(s == e){
		//d[s] = max(d1[s-1]+d2[s+1]+1-a[s],d[s]);
		return;
	}
	int m = (s+e)>>1;
	lld res;
	divide(s,m);
	divide(m+1,e);
	cht.init();
	for(lld i=s-1; i<m; i++){
		cht.add(-i,d1[i]+sum[i]+(i*(i-1)/2));
	}
	for(lld i=m+1; i<=e; i++){
        tmp[i] = cht.getv(i)+(i*(i+1)/2)-sum[i]+d2[i+1];
	}
	res = -Linf;
	for(lld i=e; i>=m+1; i--){
        res = max(res,tmp[i]);
        d[i] = max(res,d[i]);
	}
	cht.init();
	for(lld i=m+2; i<=e+1; i++){
		cht.add(-i,d2[i]-sum[i-1]+(i*(i+1)/2));
	}
	res = -Linf;
	for(lld i=s; i<=m; i++){
        res = max(cht.getv(i)+(i*(i-1)/2)+sum[i-1]+d1[i-1],res);
		d[i] = max(res,d[i]);
	}
}

int main(){
	scanf("%d",&N);
	for(int i=1; i<=N; i++){
        scanf("%lld",&a[i]);
        d[i] = -Linf;
	}
	setting(d1);
	reverse(a+1,a+N+1); setting(d2); reverse(a+1,a+N+1); reverse(d2+1,d2+N+1);
	for(int i=1; i<=N; i++) sum[i] = sum[i-1]+a[i];
	divide(1,N);
	scanf("%d",&M);
	for(int i=1; i<=M; i++){
		int x; lld y;
		scanf("%d %lld",&x,&y);
		printf("%lld\n",max(d1[x-1]+d2[x+1],d[x]+a[x]-y));
	}

	return 0;
}
