//ラブライブ！サンシャイン！！
//AT2274 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=9223372036854775807ll;

struct line{
	ll k,b;
	line(ll k=0,ll b=0):k(k),b(b){}
	ll get(ll x){return k*x+b;}
}st[300010],u;

int tp;

double its(line a,line b){
	return (b.b-a.b)/double(a.k-b.k);
}

int t[300010],n;
ll s[300010],f[300010],g[300010];
void dp(ll*f){
	int i;
	for(int i=1;i<=n;i++) s[i]=s[i-1]+t[i];
	tp=1;
	st[1]=line(0,0);
	for(int i=1;i<=n;i++){
		while(tp>1&&st[tp].get(i)<=st[tp-1].get(i)) tp--;
		f[i]=max(st[tp].get(i)+((ll)i*i+i)/2-s[i],f[i-1]);
		u=line(-i,f[i]+((ll)i*i-i)/2+s[i]);
		while(tp>1&&its(u,st[tp-1])>=its(st[tp],st[tp-1])) tp--;
		st[++tp]=u;
	}
}
ll h[300010];
void solve(int l,int r){
	if(l==r){
		h[l]=1ll-t[l];
		return;
	}
	int mid,i,now;
	ll mx;
	mid=(l+r)>>1;
	solve(l,mid);
	solve(mid+1,r);
	tp=0;
	for(int i=l-1;i<mid;i++){
		u=line(-i,f[i]+((ll)i*i-i)/2+s[i]);
		while(tp>1&&its(u,st[tp-1])>=its(st[tp],st[tp-1])) tp--;
		st[++tp]=u;
	}
	now=1;
	mx=-inf;
	for(i=r;i>mid;i--){
		while(now<tp&&its(st[now],st[now+1])>=i)now++;
        mx=max(mx,st[now].get(i)+((ll)i*i+i)/2-s[i]+g[i+1]);
        h[i]=max(h[i],mx);
	}
	tp=0;
	for(i=mid+1;i<=r;i++){
        u=line(-i,g[i+1]+((ll)i*i+i)/2-s[i]);
        while(tp>1&&its(u,st[tp-1])>=its(st[tp],st[tp-1]))tp--;
        st[++tp]=u;
    }
    now=tp;
    mx=-inf;
    for(i=l-1;i<mid;i++){
        while(now>1&&its(st[now],st[now-1])<=i)now--;
        mx=max(mx,st[now].get(i)+((ll)i*i-i)/2+s[i]+f[i]);
        h[i+1]=max(h[i+1],mx);
    }
}
int main(){

	int i,m,x,y;
	cin>>n;
	for(i=1;i<=n;i++) scanf("%d",t+i);
	dp(f);
	reverse(t+1,t+n+1);
	dp(g);
	reverse(t+1,t+n+1);
	reverse(g+1,g+n+1);
	for(i=1;i<=n;i++)s[i]=s[i-1]+t[i];
    solve(1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&x,&y);
        printf("%lld\n",max(f[x-1]+g[x+1],h[x]+t[x]-y));
    }
}