#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300005;
int n,Q,a[N];ll s[N],f[N],g[N],v[N];
int q[N],qr=0,r=0;
inline ll Y(ll *p,int i){
	return ((p[i]+s[i])<<1)-i+1ll*i*i;
}
inline ll calc(ll *p,int i,int j){
	return p[j]+(1ll*(i-j)*(i-j+1)>>1)+s[j]-s[i];
}
inline int midit(ll *p,int x){
	int L=1,R=r,mid,ret=L,lm,rm;
	while(L<R){
		mid=(L+R)>>1;
		lm=(L+mid)>>1;rm=(mid+1+R)>>1;
		if(calc(p,x,q[lm])<=calc(p,x,q[rm]))ret=rm,L=lm+1;
		else ret=lm,R=rm-1;
	}
	return ret;
}
inline void XL(ll *p){
	r=0;q[++r]=0;
	for(int i=1,t;i<=n;i++){
		s[i]=s[i-1]+a[i];
		t=q[midit(p,i)];
		p[i]=calc(p,i,t);
		p[i]=max(p[i],p[i-1]);
		while(r>1 && (Y(p,q[r])-Y(p,q[r-1]))*(i-q[r])<=(Y(p,i)-Y(p,q[r]))*(q[r]-q[r-1]))r--;
		q[++r]=i;
	}
}
int H=0;
inline void solve(int l,int r,ll *pre,ll *suf,ll *w){
	if(l==r){w[l]=1-a[l];return ;}
	int mid=(l+r+H)>>1;
	solve(l,mid,pre,suf,w);solve(mid+1,r,pre,suf,w);
	qr=0;q[++qr]=l-1;
	for(int i=l;i<=mid;i++){
		while(qr>1 && (Y(pre,q[qr])-Y(pre,q[qr-1]))*(i-q[qr])<=(Y(pre,i)-Y(pre,q[qr]))*(q[qr]-q[qr-1]))qr--;
		q[++qr]=i;
	}
	for(int i=mid+1;i<=r;i++){
		while(qr>1 && Y(pre,q[qr])-Y(pre,q[qr-1])<=1ll*(i<<1)*(q[qr]-q[qr-1]))qr--;
		v[i]=calc(pre,i,q[qr])+suf[i+1];
	}
	w[r]=max(w[r],v[r]);
	for(int i=r-1;i>mid;i--)v[i]=max(v[i],v[i+1]),w[i]=max(w[i],v[i]);
}
ll suf[N],pre[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	XL(f);
	reverse(a+1,a+n+1);
	XL(g);
	reverse(a+1,a+n+1);reverse(g+1,g+n+1);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	solve(1,n,f,g,pre);
	reverse(a+1,a+n+1);reverse(f+1,f+n+1);reverse(g+1,g+n+1);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	H=-1;solve(1,n,g,f,suf);
	reverse(suf+1,suf+n+1);reverse(a+1,a+n+1);
	reverse(f+1,f+n+1);reverse(g+1,g+n+1);
	scanf("%d",&Q);
	int x,y;
	while(Q--){
		scanf("%d%d",&x,&y);
		printf("%lld\n",max(f[x-1]+g[x+1],max(suf[x],pre[x])-y+a[x]));
	}
	return 0;
}
