#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL sum[300003], pref[300003], suff[300003];
int t[300003];

bool Q;
struct Line {
    mutable LL k, m, p;
    bool operator<(const Line& o) const {
        return Q ? p < o.p : k < o.k;
    }
};
 
struct LineContainer : multiset<Line> {
    const LL inf = LLONG_MAX;
    void init(){
        clear();
    }
    LL div(LL a, LL b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(LL k, LL m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    LL query(LL x) {
        if(empty()) return -1e18;
        Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
        if(l.k*1.0*x + l.m >= 1e18) return 1e18;
        return l.k * x + l.m;
    }
}dpL, dpR;

int n, m;
LL dp[300003];
void dfs(int s, int e){
    int mid = (s+e)/2;

    LL res = 1 - t[mid];
    if(mid != 1) res += pref[mid-2];
    if(mid != n) res += suff[mid+2];
    dp[mid] = max(dp[mid], res);

    if(s >= e) return;

    dfs(s, mid);
    dfs(mid+1, e);

    dpL.init();
    dpR.init();
    for(int i=s;i<=mid;i++){
        LL m = -2*i, b = +2*sum[i-1] + i*1ll*i - 3*i + 2;
        if(i != 1) b += 2*pref[i-2];
        dpL.add(m, b);
    }
    for(int i=mid+1;i<=e;i++){
        LL m = -2*(n-i+1), b = +2*(sum[n] - sum[i]) + (n-i+1)*1ll*(n-i+1) - 3*(n-i+1) + 2;
        if(i != n) b += 2*suff[i+2];
        dpR.add(m, b);
    }

    LL mx = -1e18;
    for(int i=s;i<=mid;i++){
        LL res = (dpR.query(n-i+1) - 2*(sum[n] - sum[i-1]) + (n-i+1)*1ll*(n-i+1) + 3*(n-i+1))/2;
        if(i != n) res += pref[i-2];
        mx = max(mx, res);
        dp[i] = max(dp[i], mx);
    }

    mx = -1e18;
    for(int i=e;i>=mid+1;i--){
        LL res = (dpL.query(i) - 2*sum[i] + i*1ll*i + 3*i)/2;
        if(i != n) res += suff[i+2];
        mx = max(mx, res);
        dp[i] = max(dp[i], mx);
    }
}

int main(){
    scanf("%d", &n);   
    for(int i=1;i<=n;i++) scanf("%d", &t[i]), sum[i] = sum[i-1] + t[i], dp[i] = -1e18;

    for(int i=1;i<=n;i++){
        if(i != 1) pref[i] = pref[i-2] + 1 - t[i];
        else pref[i] = 1 - t[i];
        pref[i] = max(pref[i], (dpL.query(i) - 2*sum[i] + i*1ll*i + 3*i)/2);
        pref[i] = max(pref[i], pref[i-1]);
        LL m = -2*i, b = +2*sum[i-1] + i*1ll*i - 3*i + 2;
        if(i != 1) b += 2*pref[i-2];
        dpL.add(m, b);
    }

    for(int i=n;i>=1;i--){
        if(i != n) suff[i] = suff[i+2] + 1 - t[i];
        else suff[i] = 1 - t[i];
        suff[i] = max(suff[i], (dpR.query(n-i+1) - 2*(sum[n] - sum[i-1]) + (n-i+1)*1ll*(n-i+1) + 3*(n-i+1))/2);
        suff[i] = max(suff[i], suff[i+1]);
        LL m = -2*(n-i+1), b = +2*(sum[n] - sum[i]) + (n-i+1)*1ll*(n-i+1) - 3*(n-i+1) + 2;
        if(i != n) b += 2*suff[i+2];
        dpR.add(m, b);
    }
    dfs(1, n);
    scanf("%d", &m);
    for(int i=1;i<=m;i++){
        int p, x;
        scanf("%d%d", &p, &x);
        printf("%lld\n", max(dp[p] + t[p] - x, pref[p-1] + suff[p+1]));
    }
}

Measured memory_bytes: 13184