// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 300000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

int N;

LL T[MAXN+5],sum[MAXN+5];

LL L[MAXN+5],R[MAXN+5];

int que[MAXN+5];

LL f[MAXN+5],h[MAXN+5],g[MAXN+5],ans[MAXN+5];

LL GetY(int j)

{

	return 1LL*f[j]+(1LL*j*j-1LL*j)/2LL+sum[j];

}

void Rev(LL seq[])

{

	for(int i=1;i<=N/2;i++)

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

}

void DP()

{

	int s=0,t=0;

	que[t++]=0;

	fill(f+1,f+1+N,-INF);

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

	{

		while(s<t-1)

		{

			int j1=que[t-2],j2=que[t-1];

			LL y1=GetY(j1),y2=GetY(j2);

			if((y1-y2)>1LL*i*(1LL*j1-1LL*j2))

				t--;

			else

				break;

		}

		int j=que[t-1];

		f[i]=f[j]+((1LL*i-1LL*j)*(1LL*i-1LL*j+1LL))/2LL-(1LL*sum[i]-1LL*sum[j]);

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

		while(s<t-1)

		{

			int j1=que[t-2],j2=que[t-1];

			LL y1=GetY(que[t-2]),y2=GetY(que[t-1]),y3=GetY(i);

			if((1LL*y1-1LL*y2)*(1LL*j2-1LL*i)<(1LL*y2-1LL*y3)*(1LL*j1-1LL*j2))

				que[--t]=0;

			else

				break;

		}

		que[t++]=i;

	}

}

void MergeSort(int l,int r)

{

	if(l==r)

	{

		if(l!=0)

			g[l]=max(g[l],L[l-1]+R[l+1]+1LL-(sum[l]-sum[l-1]));

		else

			g[l]=0;

		return;

	}

	int mid=(l+r)/2;

	MergeSort(l,mid);

	int s=0,t=0;

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

	{

		f[i]=L[i];

		while(s<t-1)

		{

			int j1=que[t-2],j2=que[t-1];

			LL y1=GetY(que[t-2]),y2=GetY(que[t-1]),y3=GetY(i);

			if((1LL*y1-1LL*y2)*(1LL*j2-1LL*i)<(1LL*y2-1LL*y3)*(1LL*j1-1LL*j2))

				que[--t]=0;

			else

				break;

		}

		que[t++]=i;

	}

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

	{

		while(s<t-1)

		{

			int j1=que[t-2],j2=que[t-1];

			LL y1=GetY(j1),y2=GetY(j2);

			if((y1-y2)>1LL*i*(1LL*j1-1LL*j2))

				t--;

			else

				break;

		}

		int j=que[t-1];

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

	}

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

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

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

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

	MergeSort(mid+1,r);

}

int main()

{

	fill(ans+1,ans+1+MAXN,-INF);

	scanf("%d",&N);

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

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

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

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

	//处理初始DP

	//处理前缀DP数组 

	DP();

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

		L[i]=f[i];

	//处理后缀DP数组 

	Rev(T);

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

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

	DP();

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

		R[i]=f[N-i+1];

	Rev(T);

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

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

	//处理完成 

	//开始CDQ分治(计算必须选择某个元素的最大值)

	//先从左往右算贡献

	fill(f+1,f+1+N,-INF);

	fill(h+1,h+1+N,-INF);

	fill(g+1,g+1+N,-INF);

	MergeSort(0,N);

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

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

	//再从右往左算贡献 

	Rev(T);

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

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

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

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

	fill(f+1,f+1+N,-INF);

	fill(h+1,h+1+N,-INF);

	fill(g+1,g+1+N,-INF);

	MergeSort(0,N);

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

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

	Rev(T);

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

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

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

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

	//预处理完成 

	//开始回答询问

	int M,P;

	LL X;

	scanf("%d",&M);

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

	{

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

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

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

	}

	return 0;

}

/*

4

3 5 1 6

5

2 1

4 2

3 1

1 1



*/

// Faster C++ solution for the same problem (measured speedup: 2.6303309832045385x):
#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);

	}

}

*/



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(stk[top - 1], stk[top]) <= slope1(stk[top - 1], i)) top--; 

		stk[++top] = i; 

	}

	ll mx = -INF, hd = 1; 

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

	{

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

		j = stk[hd], mx = max(mx, calc1(i, j)); 

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

	}

	top = 0;

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

	{

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

		stk[++top] = i; 

	}

	mx = -INF; 

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

	{

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

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

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

	}

}



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; 

}