// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=300005;



long long N,T[MAXN];

long long q[MAXN],head,tail;

long long sum[MAXN],y[MAXN];

long long L[MAXN],R[MAXN],f[MAXN],g[MAXN],h[MAXN];



void DP(long long dp[],long long N)

{

	q[head=tail=1]=0;

	y[0]=0;

	for(long long i=1;i<=N;i++)

	{

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail];

			if((y[b]-y[a])<1LL*i*(b-a))

				tail--;

			else

				break;

		}

		long long j=q[tail];

		dp[i]=max(dp[i-1],dp[j]+(i-j)*(i-j-1)/2+(i-j)-sum[i]+sum[j]);

		y[i]=dp[i]+1LL*(i-1)*i/2+sum[i];

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail],c=i;

			if((y[b]-y[a])*(c-b)<1LL*(y[c]-y[b])*(b-a))

				tail--;

			else

				break;

		}

		q[++tail]=i;

	}

}



void CDQ(long long l,long long r,long long mode)

{

	if(l==r)

	{

		f[l]=max(f[l],L[l-1]+R[r+1]+1-T[l]);

		return;

	}

	long long mid=(l+r+mode)/2;

	CDQ(l,mid,mode);

	CDQ(mid+1,r,mode);

	

	q[head=tail=1]=l-1;

	g[l-1]=L[l-1];

	y[l-1]=g[l-1]+(l-1-1)*(l-1)/2+sum[l-1];

	for(long long i=l;i<=mid;i++)

	{

		g[i]=L[i];

		y[i]=g[i]+1LL*(i-1)*i/2+sum[i];

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail],c=i;

			if((y[b]-y[a])*(c-b)<1LL*(y[c]-y[b])*(b-a))

				tail--;

			else

				break;

		}

		q[++tail]=i;

	}

	

	for(long long i=mid+1;i<=r;i++)

	{

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail];

			if((y[b]-y[a])<1LL*i*(b-a))

				tail--;

			else

				break;

		}

		long long j=q[tail];

		g[i]=g[j]+(i-j)*(i-j-1)/2+(i-j)-sum[i]+sum[j]+R[i+1];

	}

	

	for(long long i=r-1;i>mid;i--)

		g[i]=max(g[i],g[i+1]);

	for(long long i=mid+1;i<=r;i++)

		f[i]=max(f[i],g[i]);

}



int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	

	scanf("%lld",&N);

	for(long long i=1;i<=N;i++)

		scanf("%lld",&T[i]);

	

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	DP(L,N);

	reverse(T+1,T+N+1);

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	DP(R,N);

	reverse(R+1,R+N+1);



	memset(h,0x80,sizeof h);

	

	for(long long i=1;i<=N;i++)

		swap(L[i],R[N-i+1]);

	

	memset(f,0x80,sizeof f);

	CDQ(1,N,-1);

	for(long long i=1;i<=N;i++)

		h[i]=max(h[i],f[N-i+1]);



	reverse(T+1,T+N+1);

	for(long long i=1;i<=N;i++)

		swap(L[i],R[N-i+1]);

	

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	

	memset(f,0x80,sizeof f);

	CDQ(1,N,0);

	for(long long i=1;i<=N;i++)

		h[i]=max(h[i],f[i]);

	

	long long M,P,X;

	scanf("%lld",&M);

	while(M--)

	{

		scanf("%lld%lld",&P,&X);

		long long ans=max(L[P-1]+R[P+1],h[P]+T[P]-X);

		printf("%lld\n",ans);

	}

	

	return 0;

}


// Optimized solution to the same problem (faster):
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

const int N = 3e5 + 5; 

typedef long long ll;

const ll INF = 1e16; 

using namespace std;



int n, m, stk[N], top; 

ll s[N], f[N], g[N], t[N], *dp; 



template < typename T >

inline T read()

{

	T x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * w; 

}



double X(int j) { return j; }

double Y(int j) { return dp[j] + ((ll)j * j - j) / 2 + s[j]; }

double slope(int i,int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }

ll calc(int i,int j) { return dp[j] + ((ll)(i - j + 1) * (i - j)) / 2 - (s[i] - s[j]); }

void DP()

{

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

	stk[top = 1] = 0;

	for(int i = 1;i <= n;i++)

	{

		while(top > 1 && calc(i,stk[top]) <= calc(i,stk[top - 1])) top--; 

		dp[i] = max(calc(i,stk[top]),dp[i - 1]); 

		while(top > 1 && slope(stk[top - 1],i) >= slope(stk[top],stk[top - 1])) top--;

		stk[++top] = i;

	}

}



double X1(int j) { return j; }

double Y1(int j) { return f[j] + s[j] + ((ll)j * j - j) / 2; }

double slope1(int i,int j) { return (Y1(i) - Y1(j)) / (X1(i) - X1(j)); }

ll calc1(int i,int j)

{ return g[i + 1] + ((ll)(i - j) * (i - j + 1)) / 2 - (s[i] - s[j]) + f[j]; }



double X2(int j) { return j; }

double Y2(int j) { return g[j + 1] + ((ll)j * j + j) / 2 - s[j]; }

double slope2(int i,int j) { return (Y2(i) - Y2(j)) / (X2(i) - X2(j)); }

ll calc2(int i,int j)

{ return f[i] + ((ll)(j - i) * (j - i + 1)) / 2 - (s[j] - s[i]) + g[j + 1]; }



ll h[N];

void solve(int l,int r)

{

	if(l == r) { h[l] = 1 - t[l];return; }

	int mid = l + r >> 1;solve(l,mid),solve(mid + 1,r);

	top = 0;

	for(int i = l - 1;i < mid;i++)

	{

		while(top > 1 && slope1(i,stk[top - 1]) >= slope1(stk[top],stk[top - 1])) top--;

		stk[++top] = i;

	}int head = 1;ll maxx = -INF;

	for(int i = r;i > mid;i--)

	{

		while(head < top && calc1(i,stk[head]) <= calc1(i,stk[head + 1])) head++;

		maxx = max(maxx,calc1(i,stk[head]));

		h[i] = max(h[i],maxx);

	}top = 0;

	for(int i = mid + 1;i <= r;i++)

	{

		while(top > 1 && slope2(i,stk[top - 1]) >= slope2(stk[top],stk[top - 1])) top--;

		stk[++top] = i;

	}maxx = -INF;

	for(int i = l - 1;i < mid;i++)

	{

		while(top > 1 && calc2(i,stk[top]) <= calc2(i,stk[top - 1])) top--;

		maxx = max(maxx,calc2(i,stk[top]));

		h[i + 1] = max(h[i + 1],maxx);

	}

}



int main()

{

	n = read <int> (); 

	for(int i = 1; i <= n; i++) t[i] = read <int> (); 

	dp = f, DP(), reverse(t + 1, t + n + 1), dp = g, DP(); 

	reverse(t + 1, t + n + 1), reverse(g + 1, g + n + 1); 

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

	solve(1, n), m = read <int> (); 

	for(int pos, v, i = 1; i <= m; i++)

	{

		pos = read <int> (), v = read <int> ();

		printf("%lld\n", max(f[pos - 1] + g[pos + 1], h[pos] + t[pos] - v)); 

	}

	return 0; 

}

// Fastest known solution for this problem: