#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define feach(it, v) for (vector<rec>::iterator it = (v).begin(); it != (v).end(); ++ it)
#define pb push_back
#define ri rd<int>
using namespace std;
typedef long long LL;
const int maxN = 3e5 + 7;
const LL INF = 1LL << 61;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

struct rec {
	LL v; int i;
};

int n, m;
LL a[2][maxN], s[2][maxN], f[2][maxN], g[2][maxN];
vector<rec> ask[2][maxN];
LL ans[maxN];

inline void Max(LL &x, LL y) {
	if (y > x) x = y;
}

inline LL eval(LL *f, LL *s, LL x) {
	return 2LL * (f[x] + s[x]) + x * x - x;
}

inline LL up(int x, int y, LL *f, LL *s) {
	return eval(f, s, y) - eval(f, s, x);
}

inline LL dw(int x, int y) {return y - x;}

void pre(int kd) {
	static int q[maxN];
	int h = 1, t = 0;
	q[++t] = 0;
	rep (i, 1, n) s[kd][i] = s[kd][i - 1] + a[kd][i];

	f[kd][0] = 0;
	rep (i, 1, n) {
		f[kd][i] = f[kd][i - 1];
		while (h < t && up(q[t - 1], q[t], f[kd], s[kd]) < 2LL * i * dw(q[t - 1], q[t])) -- t;
		int j = q[t];
		Max(f[kd][i], f[kd][j] + 1LL * (i - j) * (i - j + 1) / 2 - s[kd][i] + s[kd][j]);
		while (h < t && up(q[t - 1], q[t], f[kd], s[kd]) * dw(q[t], i) < up(q[t], i, f[kd], s[kd]) * dw(q[t - 1], q[t])) -- t;
		q[++t] = i;
	}
}

void gao(int kd, int l, int r, int mid) {
	static int q[maxN];
	int h = 1, t = 0;
	q[++t] = l - 1;

	rep (i, l, mid) {
		g[kd][i] = f[kd][i];
		while (h < t && up(q[t - 1], q[t], g[kd], s[kd]) * dw(q[t], i) < up(q[t], i, g[kd], s[kd]) * dw(q[t - 1], q[t])) -- t;
		q[++t] = i;
	}
	rep (i, mid + 1, r) {
		while (h < t && up(q[t - 1], q[t], g[kd], s[kd]) < 2LL * i * dw(q[t - 1], q[t])) -- t;
		int j = q[t];
		g[kd][i] = g[kd][j] + 1LL * (i - j) * (i - j + 1) / 2 - s[kd][i] + s[kd][j];
	}
	per (i, r, mid + 1) {
		g[kd][i] += f[kd ^ 1][n - i];
		if (i < r) Max(g[kd][i], g[kd][i + 1]);
		feach(it, ask[kd][i])
			Max(ans[it -> i], g[kd][i] + a[kd][i] - (it -> v));
	}
}

void solve(int l, int r) {
	int mid = (l + r) >> 1;
	if (l >= r) return; // only include i is always bad ( + 1 - a)
	solve(l, mid - 1);
	solve(mid + 1, r);
	gao(0, l, r, mid);
	gao(1, n - r + 1, n - l + 1, n - (mid + 1) + 1);
}

int main() {

	n = ri();
	rep (i, 1, n) a[0][i] = a[1][n + 1 - i] = ri();
	pre(0), pre(1);

	m = ri();
	rep (i, 1, m) {
		int p = ri(), v = ri();
		ask[0][p].pb((rec){v, i});
		ask[1][n - p + 1].pb((rec){v, i});
		ans[i] = f[0][p - 1] + f[1][n - p]; // i not included
	}

	solve(1, n);
	rep (i, 1, m) 
		printf("%lld\n", ans[i]);

	return 0;
}