#include<bits/stdc++.h>
#define mo 1000000007
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long maxx(long long u,long long v){
	return u>v?u:v;
}
long long n,i,t[300005],s[300005],k[300005],b[300005],book[300005],kk,bb,tail;
long long p1,p2,p3,f[300005],g[300005],dp[300005],h[300005],m,p,x;
void gb(long long u,long long v){
	if(u==v){
		h[v]=maxx(h[v],f[v-1]+g[v+1]+1-t[v]);
		return;
	}
	long long mid=(u+v>>1);
	gb(u,mid);
	gb(mid+1,v);
	tail=0;
	for(i=u;i<=mid;i++){
		while(tail>=2){
			if(i>=book[tail])
				tail--;
			else
				break;
		}
		kk=-i;
		bb=f[i-1]+s[i-1]+((i*i-i*3)>>1);
		while(tail>=2){
			p1=(bb-b[tail])/(k[tail]-kk)+1;
			if(p1>=book[tail])
				tail--;
			else
				break;
		}
		tail++;
		k[tail]=kk;
		b[tail]=bb;
		book[tail]=(bb-b[tail-1])/(k[tail-1]-kk)+1;
	}
	for(i=mid+1;i<=v;i++){
		while(tail>=2){
			if(i>=book[tail])
				tail--;
			else
				break;
		}
		dp[i]=k[tail]*i+b[tail]+(i*i+i*3)/2+g[i+1]-s[i]+1;
	}
	for(i=v-1;i>mid;i--)
		dp[i]=maxx(dp[i+1],dp[i]);
	for(i=v;i>mid;i--)
		h[i]=maxx(h[i],dp[i]);
	tail=0;
	for(i=mid+1;i<=v;i++){
		kk=-i;
		bb=g[i+1]-s[i]+(i*i+i*3)/2;
		if(bb>b[tail]||tail==0){
			while(tail>=2){
				p1=(bb-b[tail])/(k[tail]-kk)+1;
				if(p1>=book[tail])
					tail--;
				else
					break;
			}
			tail++;
			k[tail]=kk;
			b[tail]=bb;
			book[tail]=(bb-b[tail-1])/(k[tail-1]-kk)+1;
		}
	}
	for(i=u;i<=mid;i++){
		while(tail>=2){
			if(i>=book[tail])
				tail--;
			else
				break;
		}
		dp[i]=k[tail]*i+b[tail]+(i*i-i*3)/2+f[i-1]+s[i-1]+1;
	}
	for(i=u+1;i<=mid;i++)
		dp[i]=maxx(dp[i-1],dp[i]);
	for(i=u;i<=mid;i++)
		h[i]=maxx(h[i],dp[i]);
}
int main(){
	n=read();
	for(i=1;i<=n;i++){
		t[i]=read();
		s[i]=s[i-1]+t[i];
	}
	for(i=1;i<=n;i++)
		h[i]=-1000000000000000000LL;
	tail=1;
	for(i=1;i<=n;i++){
		while(tail>=2){
			if(i>=book[tail])
				tail--;
			else
				break;
		}
		f[i]=maxx(k[tail]*i+b[tail]+(i*i+i)/2-s[i],f[i-1]);
		kk=-i;
		bb=f[i]+s[i]+((i*i-i)>>1);
		while(tail>=2){
			p1=(bb-b[tail])/(k[tail]-kk)+1;
			if(p1>=book[tail])
				tail--;
			else
				break;
		}
		tail++;
		k[tail]=kk;
		b[tail]=bb;
		book[tail]=(bb-b[tail-1])/(k[tail-1]-kk)+1;
	}
	for(i=1;(i<<1)<=n;i++)
		swap(t[i],t[n-i+1]);
	for(i=1;i<=n;i++)
		s[i]=s[i-1]+t[i];
	tail=1;
	for(i=1;i<=n;i++){
		while(tail>=2){
			if(i>=book[tail])
				tail--;
			else
				break;
		}
		g[i]=maxx(k[tail]*i+b[tail]+(i*i+i)/2-s[i],g[i-1]);
		kk=-i;
		bb=g[i]+s[i]+((i*i-i)>>1);
		while(tail>=2){
			p1=(bb-b[tail])/(k[tail]-kk)+1;
			if(p1>=book[tail])
				tail--;
			else
				break;
		}
		tail++;
		k[tail]=kk;
		b[tail]=bb;
		book[tail]=(bb-b[tail-1])/(k[tail-1]-kk)+1;
	}
	for(i=1;(i<<1)<=n;i++){
		swap(t[i],t[n-i+1]);
		swap(g[i],g[n-i+1]);
	}
	for(i=1;i<=n;i++)
		s[i]=s[i-1]+t[i];
	gb(1,n);
	m=read();
	while(m--){
		p=read();x=read();
		pus(maxx(h[p]+t[p]-x,f[p-1]+g[p+1]),2);
	}
   	return 0;
}

Measured memory_bytes: 21760