#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t[500010];
ll l[500010],r[500010],sum[500010],nisum[500010],w[500010],ls[500010];
int n;
struct que
{
	ll cop[500010],tim[500010];
	int head,tail;
	void clear()
	{
		for (int i=0;i<=head;i++) cop[i]=tim[i]=0;
		head=0;tail=0;
	}
	void push(int t,long long x)
	{
		while ((head>1)&&((cop[head]-cop[head-1])*(t-tim[head-1])-(x-cop[head-1])*(tim[head]-tim[head-1])<=0)) head--;
		cop[++head]=x;tim[head]=t;tail++;
	}
	long long top(int t)
	{
		if (head<tail) tail=head;
		while ((tail>1)&&(cop[tail]-t*tim[tail]<cop[tail-1]-t*tim[tail-1])) tail--;
		//cout<<tim[tail]<<endl;
		return cop[tail]-t*tim[tail];
		//long long ans=-4e18;
		//for (int i=1;i<=head;i++) ans=max(ans,cop[i]-t*tim[i]);return ans;
	}
}que;
struct que2
{
	ll cop[500010],tim[500010];
	int head,tail;
	void clear()
	{
		for (int i=0;i<=head;i++) cop[i]=tim[i]=0;
		head=0;tail=1;
	}
	void push(int t,long long x)
	{
		while ((head>1)&&((cop[head]-cop[head-1])*(t-tim[head-1])-(x-cop[head-1])*(tim[head]-tim[head-1])<=0)) head--;
		cop[++head]=x;tim[head]=t;
	}
	long long top(int t)
	{
		while ((head>tail)&&(cop[tail]-t*tim[tail]<cop[tail+1]-t*tim[tail+1])) tail++;
		//cout<<tim[tail]<<endl;
		return cop[tail]-t*tim[tail];
	}
}que2;
void work(int pl,int pr)
{
	if (pl==pr)
	{
		w[pl]=max(w[pl],l[pl-1]+r[pl+1]+1-t[pl]);
		return;
	}
	int mid=(pl+pr)>>1;
	work(pl,mid);work(mid+1,pr);
	que2.clear();//que2.push(0,0);
	for (int i=pl-1;i<=mid;i++) que2.push(i,l[i]+sum[i]+(ll)i*(i-1)/2);
	ll x=-4e18;
	for (int i=pr;i>mid;i--)
	{
		x=max(x,que2.top(i)+(ll)i*(i+1)/2-sum[i]+r[i+1]);
		w[i]=max(w[i],x);
	}
	que2.clear();//que2.push(0,0);
	for (int i=pr+1;i>mid;i--) que2.push(n-i+1,r[i]+nisum[i]+(ll)(n-i+1)*(n-i+1-1)/2);
	x=-4e18;
	for (int i=pl;i<=mid;i++)
	{
		x=max(x,que2.top(n-i+1)+(ll)(n-i+1)*(n-i+1+1)/2-nisum[i]+l[i-1]);
		w[i]=max(w[i],x);
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("myout.txt","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d",&t[i]);sum[i]=sum[i-1]+t[i];}
	for (int i=n;i>=1;i--) nisum[i]=nisum[i+1]+t[i];
	que.clear();que.push(0,0);
	for (int i=1;i<=n;i++)
	{
		l[i]=max(l[i-1],que.top(i)+(ll)i*(i+1)/2-sum[i]);
		que.push(i,l[i]+sum[i]+(ll)i*(i-1)/2);
	}
	/*reverse(t+1,t+n+1);for (int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i];
	que.clear();que.push(0,0);
	for (int i=1;i<=n;i++)
	{
		r[i]=max(r[i-1],que.top(i)+(ll)i*(i+1)/2-sum[i]);
		que.push(i,r[i]+sum[i]+(ll)i*(i-1)/2);
	}
	reverse(t+1,t+n+1);for (int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i];
	reverse(r+1,r+n+1);*/
	que.clear();que.push(0,0);
	for (int i=n;i>=1;i--)
	{
		r[i]=max(r[i+1],que.top(n-i+1)+(ll)(n-i+1)*(n-i+1+1)/2-nisum[i]);
		que.push(n-i+1,r[i]+nisum[i]+(ll)(n-i+1)*(n-i+1-1)/2);
	}
	//l[i]为前i个的dp值,r[i]为i~n的dp值 
	//for (int i=1;i<=n;i++) printf("%lld\n",r[i]);return 0;
	memset(w,214,sizeof(w));//w[i]表示强制i这个题目一定要做的最大cost 
	work(1,n);
	//for (int i=1;i<=n;i++) cout<<w[i]<<endl;
	int q;scanf("%d",&q);
	while (q--)
	{
		int p;ll x;scanf("%d%lld",&p,&x);
		printf("%lld\n",max(l[p-1]+r[p+1],w[p]+t[p]-x));
	}
}