#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int maxn=3e5+7;
typedef long long ll;
ll i,j,k,l,t,n,m,ans,x,v;
ll a[maxn],sum[maxn],d[maxn];
ll f[maxn],yi,er,F[maxn],G[maxn],an[maxn],p[maxn],q[maxn],e[maxn];
ll Q(ll x){return f[x]+sum[x]+(x*x-x)/2;}
ll S(ll x){return F[x]+sum[x]+(x*x-x)/2;}
void gao(){
    fo(i,1,n)sum[i]=sum[i-1]+a[i];
    memset(f,128,sizeof(f));f[0]=d[0]=0;d[++d[0]]=0;
    fo(i,1,n){
    	f[i]=f[i-1];
	    while(d[0]>1&&Q(d[d[0]])-i*d[d[0]]<Q(d[d[0]-1])-i*d[d[0]-1])d[0]--;
	    t=d[d[0]];
		f[i]=max(f[i],(f[t]+(i-t+1)*(i-t)/2-(sum[i]-sum[t])));
		while(d[0]>1){
			yi=d[d[0]-1],er=d[d[0]];
		    if((Q(er)-Q(i))*(yi-er)<(Q(yi)-Q(er))*(er-i))break;
		    d[0]--;
		}
		d[++d[0]]=i;
	}
}
void solve(int l,int r){
	int i,j,mid=(l+r)/2;
    if(l==r)return;
    d[0]=0;
    fo(i,l,mid){
	    while(d[0]>1){
		    yi=d[d[0]-1],er=d[d[0]];
		    if((S(er)-S(i))*(yi-er)<(S(yi)-S(er))*(er-i))break;
		    d[0]--;
		}
	    d[++d[0]]=i;
	}
	fo(i,mid+1,r){
	    while(d[0]>1&&S(d[d[0]])-i*d[d[0]]<S(d[d[0]-1])-i*d[d[0]-1])d[0]--;
	    t=d[d[0]];
	    e[i]=max(e[i],G[n-i]+F[t]+(i-t+1)*(i-t)/2-(sum[i]-sum[t]));
	}
	fod(i,r-1,mid+1)e[i]=max(e[i],e[i+1]);
	solve(l,mid);solve(mid+1,r);
}
int main(){
  //  freopen("fan.in","r",stdin);
  //  freopen("genocide.out","w",stdout);
    scanf("%lld",&n);
    fo(i,1,n)scanf("%lld",&a[i]);
    gao();fo(i,0,n)F[i]=f[i];
    reverse(a+1,a+1+n);
    gao();fo(i,0,n)G[i]=f[i];
    reverse(a+1,a+1+n);fo(i,1,n)sum[i]=sum[i-1]+a[i];
    memset(e,128,sizeof(e));
    solve(0,n);
    fo(i,1,n)p[i]=e[i];memset(e,128,sizeof(e));
    swap(F,G);reverse(a+1,a+1+n);fo(i,1,n)sum[i]=sum[i-1]+a[i];
    solve(0,n);
    fo(i,1,n)p[i]=max(p[i],e[n-i+1]);
    swap(F,G);reverse(a+1,a+1+n);
    fo(i,1,n)p[i]=max(p[i],F[i-1]+G[n-i]+1-a[i]);
    scanf("%d",&m);
    fo(i,1,m){
	    scanf("%d%d",&x,&v);
	    ans=max(F[x-1]+G[n-x],p[x]+a[x]-v);
	    printf("%lld\n",ans);
	}
}