#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n,m,a[1<<19];
ll s[1<<19],f[1<<19],g[1<<19],put[1<<19];
ll k[1<<19],b[1<<19];
ll calc(int p,int x){return k[p]*x+b[p];}
ll C2(ll x){return x*(x-1)/2;}
void add(ll*f,int i,int&r){
	ll k0=-i,b0=f[i]+s[i]+C2(i);
	while(r>1&&(b0-b[r])*(k[r-1]-k[r])>(b[r]-b[r-1])*(k[r]-k0))r--;
	k[++r]=k0,b[r]=b0;
}
void solve(ll*f){
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	int r=1;k[1]=b[1]=0;
	for(int i=1;i<=n;i++){
		while(r>1&&calc(r,i)<calc(r-1,i))r--;
		f[i]=max(f[i-1],calc(r,i)-s[i]+C2(i+1));
		add(f,i,r);
	}
}
void work(int l,int r){
	if(l==r)return;
	int mid=l+r>>1;work(l,mid);work(mid+1,r);
	int L=1,R=0;ll t=-1e18;
	for(int i=l-1;i<=r;i++)s[i]=i<l?0:s[i-1]+a[i];
	for(int i=l-1;i<=mid;i++)add(f,i,R);
	for(int i=r;i>mid;i--){
		while(L<R&&calc(L,i)<calc(L+1,i))L++;
		t=max(t,g[i+1]+calc(L,i)-s[i]+C2(i+1));
		put[i]=max(put[i],t+a[i]);
	}
	L=1,R=0;t=-1e18;
	reverse(a+l,a+1+r);mid=l+r-mid-1;
	for(int i=l-1;i<=r;i++)s[i]=i<l?0:s[i-1]+a[i];
	reverse(g+l-1,g+2+r);
	for(int i=l-1;i<=mid;i++)add(g,i,R);
	reverse(g+l-1,g+2+r);
	for(int i=r;i>mid;i--){
		while(L<R&&calc(L,i)<calc(L+1,i))L++;
		t=max(t,f[l+r-i-1]+calc(L,i)-s[i]+C2(i+1));
		put[l+r-i]=max(put[l+r-i],t+a[i]);
	}
	reverse(a+l,a+1+r);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	solve(f);
	reverse(a+1,a+1+n);
	solve(g);
	reverse(a+1,a+1+n);reverse(g+1,g+1+n);
	work(1,n);
	for(scanf("%d",&m);m--;){
		int p,x;scanf("%d%d",&p,&x);
		printf("%lld\n",max(f[p-1]+g[p+1],put[p]-x));
	}
	return 0;
}