#include <iostream>
#include <cstdio>
#include <cstring>
#define N 300005
using namespace std;
typedef long long ll;
ll a[N],L[N],R[N],tot[N],sum[N];
int n,m,s[N],top;
int D=0;
ll f[N],h[N],ans[N];
ll calc(int x,int i){
	return h[x]+tot[i-x]+sum[x]-sum[i];
}
ll suan(int p,int j){
	return 2*(h[p]-h[j]-sum[j]+sum[p])-1LL*j*j+1LL*p*p+j-p;
}
void push(int x){
	while(top>1&&suan(s[top-1],s[top])*2*(s[top]-x)<=suan(s[top],x)*2*(s[top-1]-s[top])) top--;
	s[++top]=x;
}
void solve(int l,int r){
	if(l==r){
		//f[l]=max(f[l],L[l-1]+R[r+1]+1-a[l]);
		return;
	}
	int mid=l+r+D>>1;
	top=0;
	for(int i=l-1;i<=mid;i++){
		h[i]=L[i];
		push(i);
	}
	for(int i=mid+1;i<=r;i++){
		while(top>1&&calc(s[top],i)<=calc(s[top-1],i)) top--;
		h[i]=calc(s[top],i)+R[i+1];
	}
	for(int i=r-1;i>mid;i--) h[i]=max(h[i],h[i+1]);
	for(int i=mid+1;i<=r;i++) f[i]=max(f[i],h[i]);
	solve(l,mid);
	solve(mid+1,r);
}
void dp(){
	top=1;
	s[1]=0;
	for(int i=1;i<=n;i++){
		while(top>1&&calc(s[top],i)<=calc(s[top-1],i)) top--;
		h[i]=max(h[i-1],calc(s[top],i));
		push(i);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
		tot[i]=tot[i-1]+i;
	}
	dp();
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[n-i+1],L[i]=h[i];
	dp();
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i],R[i]=h[n-i+1];
	for(int i=1;i<=n;i++) f[i]=-1e15;
	solve(1,n);
	for(int i=1;i<=n;i++) ans[i]=f[i];
	for(int i=1;i+i<=n;i++) swap(a[i],a[n-i+1]);
	for(int i=1;i<=n;i++) swap(L[i],R[n-i+1]),sum[i]=sum[i-1]+a[i];
	memset(f,0,sizeof(f));
	D=-1;
	for(int i=1;i<=n;i++) f[i]=-1e15;
	solve(1,n);
	for(int i=1;i<=n;i++) ans[i]=max(ans[i],f[n-i+1]);
	scanf("%d",&m);
	for(int i=1;i+i<=n;i++) swap(a[i],a[n-i+1]);
	for(int i=1;i<=n;i++) swap(L[i],R[n-i+1]);
	for(int i=1,x,w;i<=m;i++){
		scanf("%d%d",&x,&w);
		ll ret=max(ans[x]+a[x]-w,L[x-1]+R[x+1]);
		printf("%lld\n",ret);
	}
	return 0;
}