#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int INF = 0x3f3f3f3f;
const int64_t LINF = 1LL << 62;
const int NMAX = 300005;

int A[NMAX];
int64_t sum[NMAX], invSum[NMAX];
int64_t dpLeft[NMAX], dpRight[NMAX];

int64_t dpWith[NMAX];
int64_t aux[NMAX];

void add(int64_t dp[], int64_t sum[], deque<pair<int, int64_t>>& d, int j) {
    int64_t time = LINF;
    while (!d.empty()) {
        int pj = d.back().first;
        int64_t pb = dp[pj] + sum[pj] + (int64_t) pj * (pj - 1) / 2;
        int64_t pa = -pj;
        int64_t cb = dp[j] + sum[j] + (int64_t) j * (j - 1) / 2;
        int64_t ca = -j;
        time = (pb - cb) / (ca - pa);
        while (pa * time + pb < ca * time + cb) {
            time++;
        }
        if (d.back().second <= time) {
            d.pop_back();
        } else {
            break;
        }
    }
    if (d.empty()) {
        time = LINF;
    }
    d.push_back(make_pair(j, time));
}

void solve1(int n, int64_t dp[], int64_t sum[]) {
    dp[0] = 0;
    deque<pair<int, int64_t>> d;
    for (int i = 1; i <= n; ++i) {
        add(dp, sum, d, i - 1);
        while (SZ(d) > 1 && d.back().second <= i) {
            // cerr << i << ' ' << d.back().second << ' ' << d.back().first << endl;
            d.pop_back();
        }
        int j = d.back().first;
        int64_t cost = dp[j] + sum[j] - sum[i]
                + (int64_t) (i - j) * (i - j + 1) / 2;
        dp[i] = max(dp[i - 1], cost);
    }
}

void splitDp(int64_t dp[], int64_t sum[], int left, int right, int pivot) {
    deque<pair<int, int64_t>> d;
    for (int i = left - 1; i < pivot; ++i) {
        add(dp, sum, d, i);
    }
    for (int i = pivot; i <= right; ++i) {
        while (SZ(d) > 1 && d.back().second <= i) {
            // if (left == 1 && right == 12 && sum == ::invSum)
            //     cerr << "del " << i << ' ' << d.back().first << ' ' << d.back().second << endl;
            d.pop_back();
        }
        int j = d.back().first;
        dp[i] = dp[j] + sum[j] - sum[i]
            + (int64_t) (i - j) * (i - j + 1) / 2;
    }
}

void solve2(int n, int left, int right) {
    if (left > right) {
        return;
    }
    int mid = (left + right) / 2;
    memcpy(aux + left - 1, dpLeft + left - 1, (right - left + 2) * sizeof(int64_t));
    splitDp(aux, sum, left, right, mid);
    for (int i = right; i >= mid; --i) {
        aux[i] += dpRight[n - (i + 1) + 1];
    }
    for (int i = right - 1; i >= mid; --i) {
        aux[i] = max(aux[i], aux[i + 1]);
    }
    for (int i = mid; i <= right; ++i) {
        dpWith[i] = max(dpWith[i], aux[i]);
    }
    
    int nleft = n - right + 1, nright = n - left + 1;
    int nmid = n - mid + 1;

    memcpy(aux + nleft - 1, dpRight + nleft - 1, (nright - nleft + 2) * sizeof(int64_t));
    splitDp(aux, invSum, nleft, nright, nmid);
    for (int i = left; i <= mid; ++i) {
        aux[n - i + 1] += dpLeft[i - 1];
    }
    for (int i = left + 1; i <= mid; ++i) {
        aux[n - i + 1] = max(aux[n - i + 1], aux[n - (i - 1) + 1]);
    }
    for (int i = left; i <= mid; ++i) {
        dpWith[i] = max(dpWith[i], aux[n - i + 1]);
    }

    solve2(n, left, mid - 1);
    solve2(n, mid + 1, right);
}

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
        sum[i] = sum[i - 1] + A[i];
        dpWith[i] = numeric_limits<int64_t>::min();
    }

    solve1(n, dpLeft, sum);
    reverse(A + 1, A + n + 1);
    for (int i = 1; i <= n; ++i) {
        invSum[i] = invSum[i - 1] + A[i];
    }
    solve1(n, dpRight, invSum);
    reverse(A + 1, A + n + 1);

    solve2(n, 1, n);
    
    int q;
    cin >> q;

    while (q-- > 0) {
        int pos, val;
        cin >> pos >> val;

        int64_t ans = max(dpLeft[pos - 1] + dpRight[n - (pos + 1) + 1],
                dpWith[pos] + A[pos] - val);
        //cerr << dpLeft[pos - 1] + dpRight[pos + 1] << endl;
        cout << ans << '\n';
    }
}


Measured memory_bytes: 17792