#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10;
const long long inf = 1e18;

int n, m;
long long a[maxn], f[maxn], g[maxn], y[maxn], q[maxn], sum[maxn], h[maxn], temp[maxn];

inline bool check1 (int a, int b, int k) {return y[b] - y[a] < 1LL * (b - a) * k;}
inline bool check2 (int a, int b, int k) {return 1LL * (k - b) * (y[k] - y[a]) - 1LL * (k - a) * (y[k] - y[b]) < 0;}
inline void shift (int a, int b, long long c[]) {c[a] = max (c[a], c[b] + 1LL * (a - b) * (a - b + 1) / 2 - sum[a] + sum[b]);}

void get_dp (long long f[])
{
    int st = 0, ed = 0;
    q[ed++] = 0;
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        for (; st < ed - 1 && check1 (q[ed - 2], q[ed - 1], i); ed--);
        f[i] = f[i - 1];
        shift (i, q[ed - 1], f);
        y[i] = f[i] + 1LL * i * (i - 1) / 2 + sum[i];
        for (; st < ed - 1 && check2 (q[ed - 2], q[ed - 1], i); ed--);
        q[ed++] = i;
    }
}

inline void rev (long long f[]) {for (int i = 1; i <= n / 2; i++) swap(f[i], f[n - i + 1]);}

inline void divide_conquer (long long f[], long long g[], int l, int r)
{
    if (l == r)
    {
        h[l] = max (h[l], f[l - 1] + g[r + 1] - a[l] + 1);
        return ;
    }
    if (l > r) return;
    int mid = l + r >> 1;
    int st = 0, ed = 0;
    for (int i = l - 1; i <= r; i++)
    {
        for (; st < ed - 1 && check2 (q[ed - 2], q[ed - 1], i); ed--);
        if (i < mid) q[ed++] = i, temp[i] = f[i];
        else
        {
            temp[i] = -inf;
            temp[i] = max(temp[i] , f[q[ed - 1]] + 1LL * (i - q[ed - 1]) * (i - q[ed - 1] + 1) / 2 - sum[i] + sum[q[ed - 1]] + g[i + 1]);
        }
    }
    for (int i = r - 1; i >= mid; i--) temp[i] = max (temp[i], temp[i + 1]);
    for (int i = r; i >= mid; i--) h[i] = max (h[i], temp[i]);

    divide_conquer (f, g, l, mid);
    divide_conquer (f, g, mid + 1, r);
}

int main()
{
    //freopen("C:/Users/MACHENIKE/Desktop/data.in","r",stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i);
    scanf("%d", &m);

    rev (a);
    get_dp (g); rev(g);
    rev (a);
    get_dp (f);

    for (int i = 0; i <= n + 1; i++) h[i] = -inf;
    divide_conquer (f, g, 1, n);
    rev(a); rev(g); rev(f); rev(h);
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        y[i] = g[i] + 1LL * i * (i - 1) / 2 + sum[i];
    }
    divide_conquer (g, f, 1, n);
    rev(h); rev(g); rev(f); rev(a);

    while (m--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%lld\n", max (f[u - 1] + g[u + 1], h[u] - (v - a[u])));
    }
    return 0;
}
