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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const ll inf = -TEN(18);

template<typename T>
struct CHT {
	typedef pair<T, T> P;
	deque<P> deq;

	CHT(){}

	void add(T a, T b) {
		const P p(a, b);
		while (deq.size() >= 2 && check(deq[deq.size()-2], deq[deq.size()-1], p)) deq.pop_back();
		deq.push_back(p);
	}

	T incr_query(T x) {
		while (deq.size() >= 2 && f(deq[deq.size()-2], x) >= f(deq[deq.size()-1], x)) {
			deq.pop_back();
		}
		if (deq.size() == 0) return inf;
		return f(deq.back(), x);
	}

private:
	bool check(const P &p1, const P &p2, const P &p3) {
		return (p2.first-p1.first)*(p3.second-p2.second) <=
		(p2.second-p1.second)*(p3.first-p2.first);
	}
	T f(const P &p, T x) {
		return p.first * x + p.second;
	}
};

const int maxn = 300010;

pair<V<ll>, V<ll>> calc_left(V<int> T, bool rev) {
	if (rev) {
		reverse(ALL(T));
	}
	int N = T.size();
	V<ll> dp(N + 1, inf), ac(N + 1);
	dp[0] = 0;

	rep(i, N) {
		ac[i+1] = ac[i] + T[i];
	}

	CHT<ll> cht; cht.add(0, 0);
	for (int i = 1; i <= N; ++i) {
		ll v = cht.incr_query(i) + (ll)i * (i+1) / 2 - ac[i];
		dp[i] = max(dp[i-1], v);
		cht.add(-i, (ll)i * (i-1) / 2 + ac[i] + dp[i]);
	}
	return mp(dp, ac);
}

ll use[maxn];
ll tmp[maxn];
int N;

void solve(int l, int r, bool rev, const V<ll>& ac, const V<ll>& dp, const V<ll>& dpr) { //right side of midpoint
	if (l >= r) {
		ll v = 1 - (ac[l+1] - ac[l]) + dp[l] + dpr[N-1-l];
		if (rev) {
			chmax(use[N-1-l], v);
		} else {
			chmax(use[l], v);
		}
		return ;
	}

	int m;
	if (!rev) {
		m = (l + r) / 2;
		solve(l, m, rev, ac, dp, dpr);
		solve(m + 1, r, rev, ac, dp, dpr);
	} else {
		m = N-1-(N-1-l+N-1-r)/2;
		solve(l, m-1, rev, ac, dp, dpr);
		solve(m, r, rev, ac, dp, dpr);		
	}

	for (int k = l; k <= r; ++k) {
		tmp[k] = inf;
	}

	CHT<ll> cht;
	for (int i = l; i <= m; ++i) {
		cht.add(-i, (ll)(i-1) * i / 2 + ac[i] + dp[i]);
	}
	for (int i = m; i <= r; ++i) {
		ll v = cht.incr_query(i + 1);
		if (v != inf) {
			v = v + (ll)(i+1) * (i+2) / 2 - ac[i+1] + dpr[N-1-i];
		}
		tmp[i] = v;
	}

	for (int i = r-1; i >= m; --i) {
		chmax(tmp[i], tmp[i+1]);
	}

	for (int i = m; i <= r; ++i) {
		if (rev) {
			chmax(use[N-1-i], tmp[i]);
		} else {
			chmax(use[i], tmp[i]);
		}
	}
}

int main() {
	scanf("%d", &N);
	V<int> T(N);
	rep(i, N) scanf("%d", &T[i]);

	V<ll> dpl, dpr, acl, acr;

	auto r1 = calc_left(T, 0);
	tie(dpl, acl) = r1;
	auto r2 = calc_left(T, 1);
	tie(dpr, acr) = r2;

	rep(i, N) use[i] = inf;

	solve(0, N-1, 0, acl, dpl, dpr);
	solve(0, N-1, 1, acr, dpr, dpl);

	int M; scanf("%d", &M);
	while (M--) {
		int P, X; scanf("%d %d", &P, &X);
		--P;
		ll zk = dpl[P] + dpr[N-1-P];
		ll us = use[P] + T[P] - X;
		//cerr << "not use="<< zk << ",use=" << us << endl;
		printf("%lld\n", max(zk, us));
	}

	return 0;
}

Measured memory_bytes: 28316