//ラブライブ！サンシャイン！！
//AT2274
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double du;
const ll inf=9223372036854775807ll;
struct line {
	ll k,b;//y=kx+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;
du its(line a,line b) {
	return(b.b-a.b)/du(a.k-b.k);
}
int t[300010],n;
ll s[300010],f[300010],g[300010];
void dp(ll*f) {
	int i;
	for(i=1; i<=n; i++)s[i]=s[i-1]+t[i];
	tp=1;
	st[1]=line(0,0);
	for(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(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;
	scanf("%d",&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));
	}
}