#include<bits/stdc++.h>
using namespace std;
const int N = 600010 ;

typedef long long LL ;

LL f[N] ;
LL g[N] ;
LL o[N] ;
LL s[N] ;
LL tmp[N] ;

int t ;
int n, m ;
int stk[N] ;
int base[N] ;

LL calc(LL x, LL y){
    return (x - y) * (x - y + 1) / 2ll ;
}
LL calc0(LL x, LL y){
    return (x - y) * (x - y - 1) / 2ll ;
}
LL Y(LL x){
    return f[x] + s[x] + (x * x + x) / 2ll ;
}
LL YY(LL x){
    return g[x] + s[x] + (x * x + x) / 2ll ;
}
double slope1(int x, int y){
    return 1.0 * (1.0 * Y(x) - 1.0 * Y(y)) / (1.0 * x - 1.0 * y) ;
}
double slope2(int x, int y){
    return 1.0 * (1.0 * YY(x) - 1.0 * YY(y)) / (1.0 * x - 1.0 * y) ;
}
LL Y2(LL x){
    return f[x] + s[x] + (x * x - x) / 2ll ;
}
LL YY2(LL x){
    return g[x] + s[x] + (x * x - x) / 2ll ;
}
double Slope1(int x, int y){
    return 1.0 * (1.0 * Y2(x) - 1.0 * Y2(y)) / (1.0 * x - 1.0 * y) ;
}
double Slope2(int x, int y){
    return 1.0 * (1.0 * YY2(x) - 1.0 * YY2(y)) / (1.0 * x - 1.0 * y) ;
}
void solve(int l, int r){
    if (l == r)
        return o[l] = max(o[l], f[l - 1] + g[r + 1] + 1 - base[l]), void() ;
    int mid = (l + r) >> 1 ; LL ans ;
    solve(l, mid) ; solve(mid + 1, r) ;
    s[l - 1] = s[r + 1] = 0 ; t = 0 ;
    for (int i = l ; i <= r ; ++ i)
        tmp[i] = -(1ll << 62), s[i] = s[i - 1] + base[i] ;
    for (int i = l - 1 ; i < mid ; ++ i){
        while (t > 1 && Slope1(stk[t], stk[t - 1]) <= Slope1(i, stk[t])) t--;
        stk[++ t] = i ;
    }
    for (int i = mid + 1 ; i <= r ; ++ i){
        while (t > 1 && Slope1(stk[t], stk[t - 1]) <= i) t--;
        tmp[i] = f[stk[t]] + calc(i, stk[t]) - s[i] + s[stk[t]] + g[i + 1] ;
    }
    ans = -(1ll << 62) ;
    for (int i = r ; i >= mid + 1 ; -- i)
        ans = max(ans, tmp[i]), o[i] = max(o[i], ans) ;
    t = 0 ;
    for (int i = r ; i >= l ; -- i) s[i] = s[i + 1] + base[i] ;
    for (int i = r + 1 ; i > mid + 1 ; -- i){
        while (t > 1 && Slope2(stk[t], stk[t - 1]) >= Slope2(i, stk[t])) t--;
        stk[++ t] = i ;
    }
    for (int i = mid ; i >= l ; -- i){
        while (t > 1 && Slope2(stk[t], stk[t - 1]) >= i) t--;
        tmp[i] = g[stk[t]] + calc(stk[t], i) - s[i] + s[stk[t]] + f[i - 1] ;
    }
    ans = -(1ll << 62) ;
    for (int i = l ; i <= mid ; ++ i)
        ans = max(ans, tmp[i]), o[i] = max(o[i], ans) ;
}
int main(){
    cin >> n ;
    t = 0 ; int p, x ;
    for (int i = 1 ; i <= n ; ++ i){
        scanf("%d", &base[i]),
        o[i] = - (1ll  <<  62),
        s[i] = s[i - 1] + base[i] ;
    }
    stk[++ t] = 0 ; s[n + 1] = s[n] ;
    for (int i = 1 ; i <= n + 1 ; ++ i){
        while (t > 1 && slope1(stk[t], stk[t - 1]) <= i) t--;
        f[i] = max(f[i - 1], f[stk[t]] + calc0(i, stk[t]) - s[i - 1] + s[stk[t]]) ;
        while (t > 1 && slope1(stk[t], stk[t - 1]) <= slope1(i, stk[t])) t--;
        stk[++ t] = i ;
    }
    reverse(base + 1, base + n + 1) ;
    for (int i = 1 ; i <= n + 1 ; ++ i) s[i] = s[i - 1] + base[i] ;
    t = 0 ; stk[++ t] = 0 ;
    for (int i = 1 ; i <= n + 1 ; ++ i){
        while (t > 1 && slope2(stk[t], stk[t - 1]) <= i) t--;
        g[i] = max(g[i - 1], g[stk[t]] + calc0(i, stk[t]) - s[i - 1] + s[stk[t]]) ;
        while (t > 1 && slope2(stk[t], stk[t - 1]) <= slope2(i, stk[t])) t--;
        stk[++ t] = i ;
    }
    reverse(g + 1, g + n + 1) ;
    g[0] = g[n + 1], g[n + 1] = 0 ;
    reverse(base + 1, base + n + 1) ;
    solve(1, n) ; cin >> m ;
    while (m --){
        scanf("%d%d", &p, &x) ;
        printf("%lld\n", max(f[p] + g[p], o[p] + base[p] - x)) ;
    }
    return 0 ;
}

Measured memory_bytes: 28288