#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
#define N 1000015
int n,a[N],m,st[N],tot;
ll f[N],s[N],g[N],h[N],dp[N];
inline double cal1(int x,int y)
{return 1.0*(f[x]+s[x]+(1ll*x*x-x)/2-f[y]-s[y]-(1ll*y*y-y)/2)/(1.0*(x-y));}
inline double cal2(int x,int y)
{return 1.0*(g[x]+s[x]+(1ll*x*x-x)/2-g[y]-s[y]-(1ll*y*y-y)/2)/(1.0*(x-y));}
inline double cal3(int x,int y)
{return 1.0*(g[x]-s[x-1]+(1ll*x*x+x)/2-g[y]+s[y-1]-(1ll*y*y+y)/2)/(1.0*(x-y));}
void solve(int l,int r)
{
	if(l==r)
	{
		h[l]=max(h[l],f[l-1]+g[l+1]+1-a[l]);
		return;
	}int mid=(l+r)>>1;
	tot=0;
	for(int i=l-1;i<=mid;i++)
	{
		while(tot>1&&cal1(st[tot-1],st[tot])<cal1(st[tot],i))tot--;
		st[++tot]=i;
	}
	for(int i=mid+1;i<=r;i++)
	{
		while(tot>1&&cal1(st[tot-1],st[tot])<i)tot--;
		dp[i]=f[st[tot]]+1ll*(i-st[tot])*(i-st[tot]+1)/2-s[i]+s[st[tot]]+g[i+1];
	}h[r]=max(h[r],dp[r]);
	for(int i=r-1;i>mid;i--)
	{
		dp[i]=max(dp[i],dp[i+1]);
		h[i]=max(h[i],dp[i]);
	}tot=0;
	for(int i=mid+1;i<=r+1;i++)
	{
		while(tot>1&&cal3(st[tot-1],st[tot])<cal3(st[tot],i))tot--;
		st[++tot]=i;
	}
	for(int i=l;i<=mid;i++)
	{
		while(tot>1&&cal3(st[tot-1],st[tot])<i)tot--;
		dp[i]=g[st[tot]]+1ll*(st[tot]-i)*(st[tot]-i+1)/2-s[st[tot]-1]+s[i-1]+f[i-1];
	}h[l]=max(h[l],dp[l]);
	for(int i=l+1;i<=mid;i++)
	{
		dp[i]=max(dp[i],dp[i-1]);
		h[i]=max(h[i],dp[i]);
	}
	solve(l,mid);solve(mid+1,r);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-1]+a[i],h[i]=-1e18;
	st[++tot]=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1];
		while(tot>1&&cal1(st[tot-1],st[tot])<i)tot--;
		f[i]=max(f[i],f[st[tot]]+1ll*(i-st[tot])*(i-st[tot]+1)/2-s[i]+s[st[tot]]);
		while(tot>1&&cal1(st[tot-1],st[tot])<cal1(st[tot],i))tot--;
		st[++tot]=i;
	}
	reverse(a+1,a+1+n);for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	tot=0;st[++tot]=0;
	for(int i=1;i<=n;i++)
	{
		g[i]=g[i-1];
		while(tot>1&&cal2(st[tot-1],st[tot])<i)tot--;
		g[i]=max(g[i],g[st[tot]]+1ll*(i-st[tot])*(i-st[tot]+1)/2-s[i]+s[st[tot]]);
		while(tot>1&&cal2(st[tot-1],st[tot])<cal2(st[tot],i))tot--;
		st[++tot]=i;
	}reverse(a+1,a+1+n);reverse(g+1,g+1+n);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	solve(1,n);
	scanf("%d",&m);
	while(m--)
	{
		int x,y;scanf("%d%d",&x,&y);
		printf("%lld\n",max(f[x-1]+g[x+1],h[x]+a[x]-y));
	}
}
