#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 300000;
const ll INF = (1LL<<60);
ll f[MAXN + 5], g[MAXN + 5], h[MAXN + 5];
ll S[MAXN + 5], T[MAXN + 5];
ll fk(int i) {return i;}
ll fx(int j) {return 2LL*j;}
ll fc(int i) {return 1LL*i*i + i - 2*S[i];}
ll fy(int j) {return 2*S[j] + f[j] - j + 1LL*j*j;}
double fslope(int p, int q) {return 1.0*(fy(q) - fy(p)) / (fx(q) - fx(p));}
ll gk(int i) {return -i;}
ll gx(int j) {return -2LL*j;}
ll gc(int i) {return 1LL*i*i - i + 2*S[i-1];}
ll gy(int j) {return -2*S[j-1] + g[j] + j + 1LL*j*j;}
double gslope(int p, int q) {return 1.0*(gy(q) - gy(p)) / (gx(q) - gx(p));}
int stk[MAXN + 5], tp;
int N, M;
void get_dp() {
    f[0] = 0; stk[tp = 1] = 0;
    for(int i=1;i<=N;i++) {
        while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) )
            tp--;
        f[i] = max(f[i - 1], fc(i) - fk(i)*fx(stk[tp]) + fy(stk[tp]));
        while( tp > 1 && fslope(i, stk[tp]) >= fslope(stk[tp], stk[tp-1]) )
            tp--;
        stk[++tp] = i;
    }
    g[N + 1] = 0; stk[tp = 1] = N + 1;
    for(int i=N;i>=1;i--) {
        while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) )
            tp--;
        g[i] = max(g[i + 1], gc(i) - gk(i)*gx(stk[tp]) + gy(stk[tp]));
        while( tp > 1 && gslope(i, stk[tp]) >= gslope(stk[tp], stk[tp-1]) )
            tp--;
        stk[++tp] = i;
    }
}
ll tmp[MAXN + 5];
void divide_conquer(int l, int r) {
    if( l == r ) {
        h[l] = f[l + 1] - 2*T[l] + g[r + 1] + 2;
        return ;
    }
    int mid = (l + r) >> 1;
    divide_conquer(l, mid);
    divide_conquer(mid + 1, r);
    stk[tp = 1] = l - 1;
    for(int i=l;i<mid;i++) {
        while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) )
            tp--;
        while( tp > 1 && fslope(i, stk[tp]) >= fslope(stk[tp], stk[tp-1]) )
            tp--;
        stk[++tp] = i;
    }
    for(int i=mid+1;i<=r;i++) {
        while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) )
            tp--;
        tmp[i] = fc(i) - fk(i)*fx(stk[tp]) + fy(stk[tp]) + g[i + 1];
    }
    ll p = -INF;
    for(int i=r;i>mid;i--) {
        p = max(p, tmp[i]);
        h[i] = max(h[i], p);
    }
    stk[tp = 1] = r + 1;
    for(int i=r;i>mid+1;i--) {
        while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) )
            tp--;
        while( tp > 1 && gslope(i, stk[tp]) >= gslope(stk[tp], stk[tp-1]) )
            tp--;
        stk[++tp] = i;
    }
    for(int i=mid;i>=l;i--) {
        while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) )
            tp--;
        tmp[i] = gc(i) - gk(i)*gx(stk[tp]) + gy(stk[tp]) + f[i - 1];
    }
    p = -INF;
    for(int i=l;i<=mid;i++) {
        p = max(p, tmp[i]);
        h[i] = max(h[i], p);
    }
}
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++)
        scanf("%lld", &T[i]), S[i] = S[i - 1] + T[i];
    get_dp();
//    for(int i=1;i<=N;i++) printf("%d ",f[i]);
//	printf("\n");
//	for(int i=1;i<=N;i++) printf("%d ",g[i]);
//	printf("\n"); 
	divide_conquer(1, N);
    scanf("%d", &M);
    for(int i=1;i<=M;i++) {
        int P, X; scanf("%d%d", &P, &X);
        printf("%lld\n", max(f[P-1] + g[P+1], h[P] + 2*T[P] - 2*X)/2);
    }
}

Measured memory_bytes: 17792