#include<bits/stdc++.h>
using namespace std;
#define N 333333
#define rev(a) reverse(a+1,a+n+1)
#define ll long long
 
int n,t,a[N];
long long s[N],l[N],r[N],f[N],g[N],h[N],q[N];
int read(){
	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
ll sum(int n){return (ll)n*(n+1)/2;} 
double slope(int x,int y){return (double)(g[x]-g[y])/(x-y);}
void pop(int x){for (;t>1&&slope(q[t-1],q[t])<=x;t--);}
void push(int x){
	for (;t>1&&slope(q[t-1],q[t])<=slope(q[t],x);t--);q[++t]=x;
}
void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}
void calc(ll *f){
	int i;q[t=1]=0;init_s();
	for (i=1;i<=n;i++){
		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);
		g[i]=f[i]+sum(i-1)+s[i];push(i);
	}
}
 
void solve(int x,int y){
	if (x==y) return;
	int mid=(x+y)/2;t=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]=l[q[t]]+r[i+1]+sum(i-q[t])-s[i]+s[q[t]];
	}
	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 main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]=read(),f[i]=-1e18;
	calc(l);rev(a);calc(r);rev(a);rev(r);
	init_s();solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);
	init_s();solve(0,n);rev(a);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],a[p]+f[p]-x));
	}
}