#include<set>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

template<class T> struct Line {
    T a, b;
    Line(const T a_, const T b_) : a(a_), b(b_) { }

    T eval(LL x) const {
	return a * x + b;
    }
};

//  \       /
//   \     /
//    -----
//
// f(x) = ax + b;
template<class T> struct ConvexHullTrickMaxLinear {
    using Line = ::Line<T>;

    vector<Line> lines;

    void insert(const T a, const T b) {
	if (lines.empty()) {
	    lines.emplace_back(a, b);
	} else if ((lines[0].a < a && a < lines.back().a)
		|| (lines[0].a > a && a > lines.back().a)) {
	    vector<Line> st;
	    while (!lines.empty()
		    && ((lines[0].a < a && a < lines.back().a)
			|| (lines[0].a > a && a > lines.back().a))) {
		st.push_back(lines.back());
		lines.pop_back();
	    }
	    insert(a, b);
	    while (!st.empty()) {
		insert(st.back().a, st.back().b);
		st.pop_back();
	    }
	} else {
	    if ((a <= lines[0].a && lines[0].a < lines.back().a)
		    || (a >= lines[0].a && lines[0].a > lines.back().a)) {
		reverse(lines.begin(), lines.end());
	    }
	    if (lines.back().a == a) {
		if (lines.back().b < b) lines.back().b = b;
		else return;
	    } else {
		lines.emplace_back(a, b);
	    }
	    int sz = lines.size();
	    while (sz >= 3 && cover(lines[sz-3], lines[sz-2], lines[sz-1])) {
		lines[sz-2] = lines.back();
		if (last_index == sz-2) last_index--;
		lines.pop_back();
		sz--;
	    }
	}
    }

    inline bool cover(const Line &s, const Line &t, const Line &u) const {
	if (s.a > t.a) return cover(u, t, s);
	assert(s.a < t.a);
	assert(t.a < u.a);
	return (s.b-t.b)*(u.a-t.a) >= (t.b-u.b)*(t.a-s.a);
    }

    int bisect_index_max(const T x) const {
	int lo = 0, hi = lines.size();
	while (hi - lo > 1) {
	    int m = (lo + hi) / 2;
	    if (lines[m-1].eval(x) < lines[m].eval(x)) lo = m;
	    else hi = m;
	}
	return lo;
    }

    Line bisect_max(const T x) const {
	return lines[bisect_index_max(x)];
    }

    int last_index = 0;

    Line linear_search_max(const T x) {
	amax(last_index, 0);
	amin(last_index, (int)lines.size()-1);
	while (last_index+1 < (int)lines.size() && lines[last_index].eval(x) < lines[last_index+1].eval(x)) 
	    last_index++;
	while (last_index && lines[last_index].eval(x) <= lines[last_index-1].eval(x)) 
	    last_index--;
	return lines[last_index];
    }

    void clear() {
	lines.clear();
    }
};

const LL INF = 1LL<<60;
const int MAXN = 300011;
LL sums[MAXN];

int N;
LL T[MAXN];

LL L[MAXN], R[MAXN];
LL must[MAXN], never[MAXN];
LL dp[MAXN];

void rec(LL l, LL r) {
    if (r-l <= 1) {
	if (l+1 == r) {
	    amax(must[l], (1 - T[l])*2 + L[l] + R[r]);
	}
	return;
    }
    LL m = (l+r)/2;
    assert(l < m);
    assert(m < r);

    ConvexHullTrickMaxLinear<LL> C;

    {
	for (LL x=l; x<=m; x++) {
	    C.insert(-2*x, L[x] + sums[x]*2 + x*x - x);
	}
	for (LL x=m+1; x<=r; x++) {
	    dp[x-1] = C.linear_search_max(x).eval(x) - sums[x]*2 + x*x + x + R[x];
	}
	LL z = -INF;
	for (int i=r-1; i>=m; i--) {
	    amax(z, dp[i]);
	    amax(must[i], z);
	}
    }

    C.clear();
    {
	for (LL x=r; x>m; x--) {
	    C.insert(-2*x, R[x] - sums[x]*2 + x*x + x);
	}
	for (LL x=m; x>=l; x--) {
	    dp[x] = C.linear_search_max(x).eval(x) + sums[x]*2 + x*x - x + L[x];
	}
	LL z = -INF;
	for (int i=l; i<=m; i++) {
	    amax(z, dp[i]);
	    amax(must[i], z);
	}
    }

    rec(l, m);
    rec(m+1, r);
}

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%lld", T+i);

    REP (i, N) sums[i+1] = sums[i] + T[i];

    ConvexHullTrickMaxLinear<LL> C;
    C.insert(0, 0);
    REP (i, N) {
	LL x = i+1;
	L[x] = C.linear_search_max(x).eval(x) - sums[x]*2 + x*x + x;
	amax(L[x], L[x-1]);
	C.insert(-2*x, L[x] + sums[x]*2 + x*x - x);
    }

    C.lines.clear();
    C.insert(-2*N, -sums[N]*2 + (LL)N*N + N);
    for (int i=N; i>0; i--) {
	LL x = i-1;
	R[x] = C.linear_search_max(x).eval(x) + sums[x]*2 + x*x - x;
	amax(R[x], R[x+1]);
	C.insert(-2*x, R[x] - sums[x]*2 + x*x + x);
    }

    REP (i, N) never[i] = L[i] + R[i+1];
    memset(must, 0xc0, sizeof must);
    rec(0, N);

    REP (i, N) {
	assert(must[i] % 2 == 0);
	assert(never[i] % 2 == 0);
	must[i] /= 2;
	never[i] /= 2;
    }

    int M;
    scanf("%d", &M);
    REP (i, M) {
	int p;
	LL x;
	scanf("%d%lld", &p, &x);
	p--;
	LL ans = max(must[p] + T[p] - x, never[p]);
	printf("%lld\n", ans);
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 19072