#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
#define sz(x)       int(x.size())
#define int         long long

using namespace std;

typedef pair<int, int> pii;
const int N = 3e5 + 5;
const int inf = (ll)1e18;

int operator*(const pii& x, const pii& y) {return x.fi * y.se - y.fi * x.se;}
pii operator-(const pii& x, const pii& y) {return {x.fi - y.fi, x.se - y.se};}
int ccw(const pii& a, const pii& b, const pii& c) {return (c - b) * (b - a);}
vector<pii> hull; int sz, low, high, mid, type, ptr, res;
void init(int _type) {type = _type, hull.clear(), sz = ptr = 0;}
void push(const pii& p) {
    for(; sz > 1 && ccw(hull[sz - 2], hull[sz - 1], p) * type >= 0; hull.pop_back(), --sz);
    hull.pb(p); ++sz;
}
int val(int i, int x) {return (i < sz && i >= 0)? hull[i].fi * x + hull[i].se: -inf;}
int get(int x) {
    if(hull.empty()) return -inf;
    low = 0, high = sz - 1;
    while(low <= high) {
        mid = (low + high) >> 1;
        if(val(mid, x) <= val(mid + 1, x)) low = mid + 1;
        else high = mid - 1;
    }
    return max(val(low, x), val(high, x));
}

int n, t[N], s[N], f[N], g[N], _dp[N], dp[N];

void divide(int l, int r) {
    if(l == r) {
        dp[l] = max(dp[l], f[l - 1] + g[l + 1] + 1 - s[l]);
        return;
    }
    int mid = (l + r) >> 1;
    init(1); t[l - 1] = 0;
    for(int i = l; i <= r; ++i) t[i] = t[i - 1] + s[i]; t[r + 1] = t[r];
    /// dp(i) = max f(j) + (i - j) * (i - j + 1) / 2 - t[i] + t[j]
    /// 2f(j) + 2t[j] + jj - j - 2ij + ii - 2t[i] + i
    for(int i = l - 1; i < mid; ++i)
        push({-2 * i, 2 * f[i] + 2 * t[i] + i * i - i});
    int ans = -inf;
    for(int i = r; i > mid; --i) {
        ans = max(ans, (get(i) + i * i - 2 * t[i] + i) / 2 + g[i + 1]);
        dp[i] = max(dp[i], ans);
    }
    init(-1); ans = -inf;
    /// dp(i) = g(j) + (j - i) * (j - i + 1) / 2 - t[j - 1] + t[i - 1]
    /// 2g(j) + jj - 2t[j - 1] + j - 2ij + ii + 2t[i - 1] - i
    for(int i = r + 1; i > mid + 1; --i) {
        push({-2 * i, 2 * g[i] + i * i - 2 * t[i - 1] + i});
    }
    for(int i = l; i <= mid; ++i) {
        ans = max(ans, (get(i) + i * i - i + 2 * t[i - 1]) / 2 + f[i - 1]);
        dp[i] = max(dp[i], ans);
    }
    divide(l, mid); divide(mid + 1, r);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i], t[i] = t[i - 1] + s[i];
        dp[i] = -inf;
    }
    init(1); push({0, 0});
    for(int i = 1; i <= n; ++i) {
        f[i] = max(f[i - 1], (get(i) - 2ll * t[i] + i * i + i) >> 1);
        push({-2 * i, 2ll * f[i] + i * i - i + 2 * t[i]});
    }
    init(-1);
    push({-2 * n - 2, (n + 1) * (n + 1) - 2 * t[n] + n + 1});
    for(int i = n; i >= 1; --i) {
        g[i] = max(g[i + 1], (get(i) + i * i - i + 2 * t[i - 1]) >> 1);
        push({-2 * i, 2 * g[i] + i * i - 2 * t[i - 1] + i});
    }
    divide(1, n);
    int q, pi, xi; cin >> q;
    while(q --) {
        cin >> pi >> xi;
        cout << max(f[pi - 1] + g[pi + 1], dp[pi] + s[pi] - xi) << '\n';
    }
}


Measured memory_bytes: 16640