#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define rev(a) reverse(a+1,a+n+1)
typedef long long ll;
typedef pair<int,int> P;
const int N=3e5+5,inf=1e9;
int n,i,a[N];
ll s[N],g[N],l[N],r[N],f[N];
ll sum(int n){return (ll)n*(n+1)/2;}
int t,q[N],x,k;

double cal(int x,int y){return (double)(g[x]-g[y])/(x-y);}
void pop(int x){for (;t>1&&cal(q[t-1],q[t])<=x;t--);}
void push(int x)
{
	for (;t>1&&cal(q[t-1],q[t])<=cal(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 init(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);
	}
}
ll w[N];
void work(int x,int y){
	if (x==y) return;int i,m=x+y>>1;t=0;
	for (i=x;i<=m;i++) g[i]=l[i]+sum(i-1)+s[i],push(i);
	for (;i<=y;i++) pop(i),
		w[i]=l[q[t]]+r[i+1]+sum(i-q[t])-s[i]+s[q[t]];
	for (f[y]=max(f[y],w[y]),i=y-1;i>m;i--)
		f[i]=max(f[i],w[i]=max(w[i],w[i+1]));
	work(x,m);work(m+1,y);
}

int main()
{
	for (scanf("%d",&n),i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=-inf;
	init(l);rev(a);init(r);rev(a);rev(r);
	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);
	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);
	
	for (scanf("%d",&i);i;i--)
	{
		scanf("%d%d",&x,&k);
		printf("%d\n",max(l[x-1]+r[x+1],f[x]+a[x]-k));
	}	
}
