#include <algorithm>
#include <cassert>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

class convex_hull_trick_with_monotonicity {
    typedef pair<ll, ll> line_t;
    deque<line_t> lines;
    ll inc_x, dec_x;  // only for assertions
public:
    convex_hull_trick_with_monotonicity() {
        inc_x = LLONG_MIN;
        dec_x = LLONG_MAX;
    }
    void add_line_increasing(ll a, ll b) {
        assert (lines.empty() or lines.back().first <= a);  // weakly monotonically increasing
        while (lines.size() >= 2 and not is_required(lines[lines.size() - 2], lines.back(), { a, b })) {
            lines.pop_back();
        }
        lines.emplace_back(a, b);
    }
    void add_line_decreasing(ll a, ll b) {
        assert (lines.empty() or a <= lines.front().first);  // weakly monotonically decreasing
        while (lines.size() >= 2 and not is_required({ a, b }, lines.front(), lines[1])) {
            lines.pop_front();
        }
        lines.emplace_front(a, b);
    }
    ll get_max_increasing(ll x) {
        assert (inc_x <= x);  // weakly monotonically increasing
        inc_x = x;
        assert (not lines.empty());
        while (lines.size() >= 2 and get_value(0, x) <= get_value(1, x)) {
            lines.pop_front();
        }
        return get_value(0, x);
    }
    ll get_max_decreasing(ll x) {
        assert (x <= dec_x);  // weakly monotonically decreasing
        dec_x = x;
        assert (not lines.empty());
        while (lines.size() >= 2 and get_value(-2, x) >= get_value(-1, x)) {
            lines.pop_back();
        }
        return get_value(-1, x);
    }
private:
    bool is_required(line_t f1, line_t f2, line_t f3) const {
        return (f3.first - f1.first) * (f1.second - f2.second) < (f2.first - f1.first) * (f1.second - f3.second);
    }
    ll get_value(int i, ll x) const {
        if (i < 0) i += lines.size();
        ll a, b; tie(a, b) = lines[i];
        return a * x + b;
    }
};

vector<ll> run_dp(int n, vector<ll> const & t, vector<ll> const & acc) {
    vector<ll> dp(n + 1);
    convex_hull_trick_with_monotonicity cht;
    cht.add_line_decreasing(0, 0);
    REP3 (r, 1, n + 1) {
        // max { dp(l) + (r - l + 1) C 2 - \sum T_i | l < r }
        ll use = cht.get_max_increasing(r) + r * (r + 1ll) / 2 - acc[r];
        dp[r] = max(dp[r - 1], use);
        cht.add_line_decreasing(- r, dp[r] + r * (r - 1ll) / 2 + acc[r]);
    }
    return dp;
}

vector<ll> get_ign(int n, vector<ll> const & t, vector<ll> const & dpl, vector<ll> const & dpr) {
    vector<ll> ign(n);
    REP (i, n) ign[i] = dpl[i] + dpr[i + 1];
    return ign;
}

vector<ll> get_use(int n, vector<ll> const t, vector<ll> const & acc, vector<ll> const & dpl, vector<ll> const & dpr) {
    // divide and conquer
    vector<ll> use(n, LLONG_MIN);
    function<void (int, int)> go = [&](int l, int r) {
        if (l == r) return;
        int m = (r + l) / 2;
        {  // left
            convex_hull_trick_with_monotonicity cht;
            REP3 (r1, m + 1, r + 1) {
                cht.add_line_decreasing(- r1, r1 * (r1 + 1ll) / 2 - acc[r1] + dpr[r1]);
            }
            ll y = LLONG_MIN;
            REP3 (l1, l, m + 1) {
                ll x = cht.get_max_increasing(l1) + dpl[l1] + l1 * (l1 - 1ll) / 2 + acc[l1];
                chmax(y, x);
                chmax(use[l1], y);
            }
        }
        {  // right
            convex_hull_trick_with_monotonicity cht;
            REP3 (l1, l, m + 1) {
                cht.add_line_decreasing(- l1, dpl[l1] + l1 * (l1 - 1ll) / 2 + acc[l1]);
            }
            ll y = LLONG_MIN;
            REP3R (r1, m + 1, r + 1) {
                ll x = cht.get_max_decreasing(r1) + r1 * (r1 + 1ll) / 2 - acc[r1] + dpr[r1];
                chmax(y, x);
                chmax(use[r1 - 1], y);
            }
        }
        go(l, m);
        go(m + 1, r);
    };
    go(0, n);
    return use;
}

int main() {
    // input
    int n; cin >> n;
    vector<ll> t(n);
    REP (i, n) cin >> t[i];

    // prepare

    reverse(ALL(t));
    vector<ll> acc(n + 1);
    partial_sum(ALL(t), acc.begin() + 1);
    vector<ll> dpr = run_dp(n, t, acc);
    reverse(ALL(dpr));
    reverse(ALL(t));

    acc.assign(n + 1, 0ll);
    partial_sum(ALL(t), acc.begin() + 1);
    vector<ll> dpl = run_dp(n, t, acc);

    vector<ll> ign = get_ign(n, t, dpl, dpr);
    vector<ll> use = get_use(n, t, acc, dpl, dpr);

    // query
    int m; cin >> m;
    while (m --) {
        int p; ll x; cin >> p >> x;
        -- p;

        // solve
        ll ans = max(use[p] + t[p] - x, ign[p]);

        // output
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 16640