#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp> //__gnu_pbds::priority_queue
 
using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int N = 300000;
const int oo = 0x3f3f3f3f;
 
template<typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; 
    return x *= f;
}


int n, m;
int stk[N + 5], top;
ll c[N + 5], s[N + 5];
ll a[N + 5], fl[N + 5], fr[N + 5];

void calc(ll f[]) {
    top = 0;
    for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];

#define Y(i) (2ll * (f[i] + s[i]) + 1ll * i * i)
#define slope(x, y) (double(Y(y) - Y(x)) / double(y - x))

    stk[top ++] = 0;
    for(int i = 1; i <= n; ++i) {
        while(top > 1 && slope(stk[top-2], stk[top-1]) <= 2. * i + 1.) -- top;

        int j = stk[top-1];
        f[i] = f[j] + 1ll * (i - j) * (i - j + 1) / 2 - (s[i] - s[j]);
        chkmax(f[i], f[i-1]);

        while(top > 1 && slope(stk[top-2], stk[top-1]) <= slope(stk[top-1], i)) -- top;

        stk[top ++] = i;
    }

#undef Y
#undef slope
}

ll tmp[N + 5];
void solve(int l, int r, ll f_l[], ll f_r[]) {
    int mid = (l + r) >> 1;

#define Y(i) (2ll * (f_l[i] + s[i]) + 1ll * i * i)
#define slope(x, y) (double(Y(y) - Y(x)) / double(y - x))

    top = 0;
    for(int i = l - 1; i < mid; ++i) {
        while(top > 1 && slope(stk[top-2], stk[top-1]) <= slope(stk[top-1], i)) -- top;
        stk[top ++] = i;
    }
    for(int i = mid; i <= r; ++i) {
        while(top > 1 && slope(stk[top-2], stk[top-1]) <= 2. * i + 1.) -- top;
        int j = stk[top-1];
        tmp[i] = f_r[i+1] + f_l[j] + 1ll * (i - j) * (i - j + 1) / 2 - (s[i] - s[j]);
    }
    for(int i = r - 1; i >= mid; --i) chkmax(tmp[i], tmp[i+1]);
    for(int i = mid; i <= r; ++i) chkmax(c[i], tmp[i]);

    if(l == r) return;
    solve(l, mid, f_l, f_r);
    solve(mid+1, r, f_l, f_r);

#undef Y
#undef slope
}

int main() {

    read(n); for(int i = 1; i <= n; ++i) read(a[i]);

    calc(fl);
    std::reverse(a + 1, a + n + 1);

    calc(fr);
    std::reverse(a + 1, a + n + 1);
    std::reverse(fr + 1, fr + n + 1);

    memset(c, ~oo, sizeof c);

    for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];
    solve(1, n, fl, fr);

    std::reverse(c + 1, c + n + 1);
    std::reverse(a + 1, a + n + 1);
    std::reverse(fl + 1, fl + n + 1);
    std::reverse(fr + 1, fr + n + 1);

    for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];
    solve(1, n, fr, fl);

    std::reverse(c + 1, c + n + 1);
    std::reverse(a + 1, a + n + 1);
    std::reverse(fl + 1, fl + n + 1);
    std::reverse(fr + 1, fr + n + 1);

    read(m); 
    for(int i = 1; i <= m; ++i) {
        static int p, x;
        read(p), read(x);
        printf("%lld\n", std::max(fl[p - 1] + fr[p + 1], c[p] + a[p] - x));
    }
    return 0;
}


Measured memory_bytes: 16896