//from Kuugo
#include<bits/stdc++.h>
using namespace std;
#define N 333333
#define rev(a) reverse(a+1,a+n+1)
 
int n,m;
long long t[N],s[N],l[N],r[N],f[N],g[N],h[N],q[N];
 
double slope(int i,int j){
	return (double)(g[i]-g[j])/(i-j);
}
 
void pop(int i){
	while (m>1&&slope(q[m],q[m-1])<=i) m--;
}
 
void push(int i){
	while (m>1&&slope(i,q[m])>=slope(q[m],q[m-1])) m--;
	q[++m]=i;
}
 
void calc(long long f[]){
	for (int i=1;i<=n;i++) s[i]=s[i-1]+t[i];
	q[m=1]=0;
	for (int i=1;i<=n;i++){
		pop(i);
		f[i]=max(f[i-1],g[q[m]]-1ll*i*q[m]+1ll*i*(i+1)/2-s[i]);
		g[i]=f[i]+1ll*i*(i-1)/2+s[i];
		push(i);
	}
}
 
void solve(int x,int y){
	if (x==0&&y==n) for (int i=1;i<=n;i++) s[i]=s[i-1]+t[i];
	if (x==y) return;
	int mid=(x+y)/2;m=0;
	for (int i=x;i<=mid;i++){
		g[i]=l[i]+1ll*i*(i-1)/2+s[i];
		push(i);
	}
	for (int i=mid+1;i<=y;i++){
		pop(i);
		h[i]=g[q[m]]-1ll*i*q[m]+1ll*i*(i+1)/2-s[i]+r[i+1];
	}
	for (int i=y-1;i>mid;i--) h[i]=max(h[i],h[i+1]);
	for (int i=mid+1;i<=y;i++) f[i]=max(f[i],h[i]);
	solve(x,mid);solve(mid+1,y);
}
 
int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
 
int main(){
	n=read();
	for (int i=1;i<=n;i++) t[i]=read(),f[i]=-1e18;
	calc(l);rev(t);calc(r);rev(t);rev(r);
	solve(0,n);rev(t);rev(f);rev(l);rev(r);swap(l,r);
	solve(0,n);rev(t);rev(f);rev(l);rev(r);swap(l,r);
	for (int m=read();m;m--){
		int p=read(),x=read();
		printf("%lld\n",max(l[p-1]+r[p+1],t[p]+f[p]-x));
	}
	return 0;
}