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

#define int long long

#define inf (int)1000000007
#define mod (int)1000000007

#define rep(i, n) for(int i = 0; i < (n); i++)
#define trep(i, n) for(int i = 0; i <= (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rtrep(i, n) for(int i = (n); i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define mfor(i, s, t) for(int i = (s); i < (t); i++)
#define tfor(i, s, t) for(int i = (s); i <= (t); i++)
#define rfor(i, s, t) for(int i = (t) - 1; i >= (s); i--)

class Chull1 {
	public:
	vector<pair<double, pair<int, int>>> d;
	void init() {
		d.clear();
	}
	double cross(int s, int k) {
		assert(!d.empty());
		auto w = d.back().second;
		return (double)(k - w.second) / (double)(w.first - s);
	}
	void add(int s, int k) {
		while(!d.empty()) {
			double w = cross(s, k);
			if(d.back().first > w) {
				break;
			}
			d.pop_back();
		}
		if(d.empty()) {
			d.push_back(make_pair(inf, make_pair(s, k)));
		}
		else {
			d.push_back(make_pair(cross(s, k), make_pair(s, k)));
		}
	}
	int solve(int x) {
		while(d.back().first < (double)x) {
			d.pop_back();
		}
		auto w = d.back().second;
		return w.first * x + w.second;
	}
} chull1;

class Chull2 {
	public:
	vector<pair<double, pair<int, int>>> d;
	double cross(int s, int k) {
		assert(!d.empty());
		auto w = d.back().second;
		return (double)(k - w.second) / (double)(w.first - s);
	}
	void add(int s, int k) {
		while(!d.empty()) {
			double w = cross(s, k);
			if(d.back().first < w) {
				break;
			}
			d.pop_back();
		}
		if(d.empty()) {
			d.push_back(make_pair(-inf, make_pair(s, k)));
		}
		else {
			d.push_back(make_pair(cross(s, k), make_pair(s, k)));
		}
	}
	int solve(int x) {
		while(d.back().first > (double)x) {
			d.pop_back();
		}
		auto w = d.back().second;
		return w.first * x + w.second;
	}
};

class Seg {
	public:
	int n;
	vector<Chull2> d;
	void init(int nw) {
		n = 1;
		while(n < nw) {
			n *= 2;
		}
		d.resize(n * 2);
	}
	void add_(int b, int s, int k, int p, int nb, int ne) {
		if(nb <= b && b < ne) {
			d[p].add(s, k);
			if(nb < ne - 1) {
				int m = (nb + ne) / 2;
				add_(b, s, k, p * 2 + 1, nb, m);
				add_(b, s, k, p * 2 + 2, m, ne);
			}
		}
	}
	void add(int b, int s, int k) {
		add_(b, s, k, 0, 0, n);
	}
	int solve_(int x, int b, int e, int p, int nb, int ne) {
		if(b <= nb && ne <= e) {
			return d[p].solve(x);
		}
		else if(ne <= b || e <= nb) {
			return -inf * inf;
		}
		else {
			int m = (nb + ne) / 2;
			return max(solve_(x, b, e, p * 2 + 1, nb, m), solve_(x, b, e, p * 2 + 2, m, ne));
		}
	}
	int solve(int x, int b, int e) {
		return solve_(x, b, e, 0, 0, n);
	}
} seg;

int dd[334514];

int mfr[334514];
int mbk[334514];

int ans[334514];

signed main() {
	int dn;
	cin >> dn;
	int all = 0;
	rep(i, dn) {
		cin >> dd[i];
		all += dd[i];
	}
	chull1.add(1, 0);
	mfr[0] = 0;
	rep1(i, dn) {
		chull1.add(-i * 2 + 1, i * i - i + (mfr[i - 1] + dd[i - 1]) * 2);
		mfr[i] = (i * i + chull1.solve(i)) / 2;
	}
	chull1.init();
	chull1.add(1, 0);
	mbk[dn] = 0;
	rep1(i, dn) {
		chull1.add(-i * 2 + 1, i * i - i + (mbk[dn - i + 1] + dd[dn - i]) * 2);
		mbk[dn - i] = (i * i + chull1.solve(i)) / 2;
	}
	seg.init(dn);
	rrep(i, dn) {
		seg.add(i, -i * 2 + 1, i * i - i + mfr[i] * 2);
	}
	vector<pair<pair<int, int>, pair<int, int>>> mv;
	mv.push_back(make_pair(make_pair(dn, (dn * dn + seg.solve(dn, 0, dn)) / 2), make_pair(0, dn)));
	rrep(i, dn) {
		if(mv.back().second.first == i + 1) {
			mv.pop_back();
		}
		else {
			int p = -inf * inf;
			if(mv.size() > 1) {
				p = mv[mv.size() - 2].first.second;
			}
			int k = mv.back().first.first;
			mv.back().second.second = i + 1;
			mv.back().first.second = max(p, (k * k + seg.solve(k, mv.back().second.first, i + 1)) / 2 + mbk[k]);
		}
		ans[i] = mv.back().first.second;
		while(!mv.empty()) {
			int b = mv.back().second.first;
			int e = mv.back().second.second;
			int k = mv.back().first.first;
			int bo = mfr[b] + (k - b) * (k - b + 1) / 2 + mbk[k];
			int bn = mfr[b] + (i - b) * (i - b + 1) / 2 + mbk[i];
			if(bo < bn) {
				mv.pop_back();
			}
			else {
				while(b < e - 1) {
					int m = (b + e) / 2;
					int mo = mfr[m] + (k - m) * (k - m + 1) / 2 + mbk[k];
					int mn = mfr[m] + (i - m) * (i - m + 1) / 2 + mbk[i];
					if(mo < mn) {
						e = m;
					}
					else {
						b = m;
					}
				}
				mv.back().second.second = e;
				int p = -inf * inf;
				if(mv.size() > 1) {
					p = mv[mv.size() - 2].first.second;
				}
				mv.back().first.second = max(p, (k * k + seg.solve(k, mv.back().second.first, e)) / 2 + mbk[k]);
				break;
			}
		}
		if(mv.empty() || mv.back().second.second < i) {
			int w = 0;
			int p = 0;
			if(!mv.empty()) {
				w = mv.back().second.second;
				p = mv.back().first.second;
			}
			mv.push_back(make_pair(make_pair(i, max(p, (i * i + seg.solve(i, w, i)) / 2 + mbk[i])), make_pair(w, i)));
		}
	}
	int dm;
	cin >> dm;
	rep(i, dm) {
		int p, x;
		cin >> p >> x;
		p--;
		cout << max(ans[p], mfr[p] + x + mbk[p + 1]) - (all - dd[p] + x) << endl;
	}
}


Measured memory_bytes: 75904