#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int maxn=3e5+10;

int n,m,t[maxn];
LL L[maxn],R[maxn],C[maxn],sum[maxn],tmp[maxn];

struct Point{
	LL x,y;
	Point() {}
	Point(LL x,LL y):x(x),y(y) {}
	Point operator + (const Point &p) const {return Point(x+p.x,y+p.y);}
	Point operator - (const Point &p) const {return Point(x-p.x,y-p.y);}
};
LL Cross(Point A,Point B) {return A.x*B.y-A.y*B.x;}
LL Dot(Point A,Point B) {return A.x*B.x+A.y*B.y;}

namespace my_queue{
	int top;
	Point P[maxn];

	void init() {top=0;}

	void push(Point x)
	{
		while (top>=2&&Cross(P[top]-P[top-1],x-P[top])>=0) top--;
		P[++top]=x;
	}

	LL query(LL k)
	{
		while (top>=2&&P[top].y-P[top-1].y<=k*(P[top].x-P[top-1].x)) top--;
		return P[top].y-k*P[top].x;
	}

	LL query0(LL k)
	{
		while (top>=2&&P[top].y-P[top-1].y<=k*(P[top].x-P[top-1].x)) top--;
//		printf("%lld",P[top].x);
		return P[top].y-k*P[top].x;
	}
};

void DP(LL f[])
{
	int i;
	sum[0]=0;
	for (i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	my_queue::init();
	my_queue::push(Point(0,0));
	for (i=1;i<=n;i++)
	{
		f[i]=max(f[i-1],my_queue::query(i)+(LL)i*(i+1)/2-sum[i]);
		my_queue::push(Point(i,(LL)i*(i-1)/2+sum[i]+f[i]));
	}
}

void solve(LL L[],LL R[],int s,int t)
{
	if (s==t) {C[s]=max(C[s],L[s-1]+R[s+1]-::t[s]+1); return;}

	int i,mid=(s+t)>>1;
	my_queue::init();
	for (i=s-1;i<mid;i++)
		my_queue::push(Point(i,(LL)i*(i-1)/2+sum[i]+L[i]));
	for (i=mid;i<=t;i++)
	{
		tmp[i]=my_queue::query0(i)+(LL)i*(i+1)/2-sum[i]+R[i+1];

//		printf("--->%d\n",i);
	}

//	printf("[%d,%d] [%d,%d]\n",s,mid,mid,t);
//	for (i=mid;i<=t;i++)
//		printf("%lld ",tmp[i]);
//	puts("");

	for (i=t-1;i>=mid;i--)
		tmp[i]=max(tmp[i],tmp[i+1]);


	for (i=mid;i<=t;i++)
		C[i]=max(C[i],tmp[i]);

//	if (s==t) return;


//	printf("[%d,%d] ==> [%d,%d]\n",s,mid,mid+1,t);
//	printf("C :");
//	for (i=1;i<=n;i++)
//		printf("%lld ",C[i]);
//	puts("");
//	puts("");

	solve(L,R,s,mid);
	solve(L,R,mid+1,t);
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,p,x;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&t[i]);

	DP(L);
	for (i=1;i<=n-i+1;i++)
		swap(t[i],t[n-i+1]);
	DP(R);
	for (i=1;i<=n-i+1;i++)
	{
		swap(t[i],t[n-i+1]);
		swap(R[i],R[n-i+1]);
	}

//	printf("L :");
//	for (i=1;i<=n;i++)
//		printf("%lld ",L[i]);
//	puts("");
//	printf("R :");
//	for (i=1;i<=n;i++)
//		printf("%lld ",R[i]);
//	puts("");

	memset(C,-0x3f3f3f3f,sizeof(C));

	for (i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];

	solve(L,R,1,n);

//	puts("");
//	printf("C :");
//	for (i=1;i<=n;i++)
//		printf("%lld ",C[i]);
//	puts("");

//	return 0;
	for (i=1;i<=n-i+1;i++)
	{
		swap(t[i],t[n-i+1]);
		swap(L[i],L[n-i+1]);
		swap(R[i],R[n-i+1]);
		swap(C[i],C[n-i+1]);
	}

//	puts("----------------------------");

	for (i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];

	solve(R,L,1,n);
	for (i=1;i<=n-i+1;i++)
	{
		swap(t[i],t[n-i+1]);
		swap(L[i],L[n-i+1]);
		swap(R[i],R[n-i+1]);
		swap(C[i],C[n-i+1]);
	}

//	printf("C :");
//	for (i=1;i<=n;i++)
//		printf("%lld ",C[i]);
//	puts("");

	scanf("%d",&m);
	while (m--)
	{
		scanf("%d%d",&p,&x);
		printf("%lld\n",max(L[p-1]+R[p+1],C[p]-x+t[p]));
//		printf("max(%lld+%lld,%lld-%d+%d)\n",L[p-1],R[p+1],C[p],x,t[p]);
	}
}
