#include <iostream> 
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define For(i , a , b) for (int i = a , _b = b ; i <= _b ; ++i)
#define Ford(i , a  ,b) for (int i = a , _b = b : i >= _b ; --i)
#define Rep(i , n) for (int i = 0 , _n = n ; i < _n ; ++i)
#define sz(A) ((int)A.size())
#define LL(x) (x << 1)
#define RR(x) ((x << 1) | 1)

typedef pair<int , int> pt;

const int maxn = 300000 + 123;
int n;
long long T[maxn];

//---------------------------------------------------------------------------------------
const long long INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000 + 123;
struct line
{	
	long long a,b;
};
long double intersection(const line u, const line v) {
	return (long double) (v.b - u.b) / (u.a - v.a);
}

line convexHull[maxn];
int top = 0, curPointer;
long long curPos;
void initConvexHull() {
	top = 0;
	curPointer = 0;
	curPos = INF;
}
const long double eps = 1e-8;
void pushALine(const line add) {
	while (top >= 2 
		&& intersection(add, convexHull[top])
		 <= intersection(convexHull[top], convexHull[top - 1]) + eps) 
			--top;
	convexHull[++top] = add;
	if (top == 1) curPointer = top;
	if (top > 1)
	if (curPos >= intersection(convexHull[top - 1], convexHull[top]) - eps) 
		curPointer = top;
}
long long getValue(const line u, const long long pos) {
	return u.a * pos + u.b;
}
long long query(long long pos) {
	curPos = pos;
	if (!curPointer) return 0;
	while (curPointer > 1 && pos <= intersection(convexHull[curPointer - 1],
		convexHull[curPointer]) + eps) --curPointer;
	return getValue(convexHull[curPointer], pos);
}
//--------------------------------------------------------------------------------------

void ReadData() {
	cin >> n;
	For(i,1,n) cin >> T[i];
}

long long prefixDp[maxn], suffixDp[maxn];
long long prefixSum[maxn], suffixSum[maxn];
void maximize(long long &a, const long long b) {
	if (a < b) a = b;
}

void preSolve(long long prefixDp[]) {
	prefixSum[0] = 0;
	For(i,1,n) prefixSum[i] = prefixSum[i - 1] + 1LL * T[i] * 2;

	initConvexHull();
	pushALine((line){0, 0} );
	prefixDp[0] = 0;
	For(i,1,n) {
		prefixDp[i] = prefixDp[i - 1];
		maximize(prefixDp[i], 1LL * i * i + i - prefixSum[i] + query(-2 * i));
		pushALine((line){i, 1LL * i * i - i + prefixDp[i] + prefixSum[i]});
	} 
}

long long val[maxn];
void Go(int L, int R, long long prefixSum[],long long prefixDp[], long long suffixDp[] , long long dp[]) {
	if (L > R) return;
	int mid = (L + R) >> 1;
	if (L < mid) Go(L, mid , prefixSum, prefixDp , suffixDp , dp);
	Go(mid + 1, R, prefixSum, prefixDp, suffixDp , dp);	


	/// solve the case that a segment passed mid
	initConvexHull();
	For(i,L - 1,mid - 1) {
		pushALine((line){i, 1LL * i * i - i + prefixDp[i] + prefixSum[i]});
	}

	For(i,mid,R) val[i] = -INF;
	For(i,mid,R) {
		maximize(val[i], 1LL * i * i + i - prefixSum[i] + query(-2 * i) + suffixDp[i + 1]);
	}
	for (int i = R - 1; i >= mid; i--) {
		maximize(val[i], val[i + 1]);
	}
	For(i,mid,R) maximize(dp[i], val[i]);
}

long long used[maxn];
long long dp[maxn];
void Process() {	
	For(i,0,n) used[i] = -INF;
	For(i,0,n) dp[i] = -INF;
	preSolve(prefixDp);
	reverse(T + 1, T + 1 + n);
	preSolve(suffixDp);
	reverse(T + 1, T + 1 + n);
	reverse(suffixDp + 1, suffixDp + 1 + n);

	For(i,1,n) prefixSum[i] = prefixSum[i - 1] + 1LL * 2 * T[i];
	Go(1, n, prefixSum, prefixDp, suffixDp, dp);
	For(i,1,n) maximize(used[i], dp[i]);
	

	For(i,0,n) dp[i] = -INF;
	reverse(T + 1, T + 1 + n);
	For(i,1,n) prefixSum[i] = prefixSum[i - 1] + 1LL * 2 * T[i];
	reverse(suffixDp + 1, suffixDp + 1 + n);
	reverse(prefixDp + 1, prefixDp + 1 + n);
	Go(1, n, prefixSum, suffixDp, prefixDp , dp);
	reverse(dp + 1, dp + 1 + n);
	reverse(T + 1, T + 1 + n);
	reverse(suffixDp + 1, suffixDp + 1 + n);
	reverse(prefixDp + 1, prefixDp + 1 + n);
	For(i,1,n) maximize(used[i], dp[i]);

	//For(i,1,n) cout << used[i] << " "; cout << endl;
	int q; cin >> q;
	while (q--) {
		int pos; long long val;
		cin >> pos >> val;
		val *= 2;
		long long res = 0;
		maximize(res, prefixDp[pos - 1] + suffixDp[pos + 1]);
		maximize(res, used[pos] + 2LL * T[pos]  -val);

		cout << res / 2 << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//freopen("input.inp" , "r", stdin);
	//freopen("out1.out", "w" , stdout);
	ReadData();
	Process();	

	return 0;

}			

Measured memory_bytes: 24064