#include <cstdio>
#include <algorithm>
#include <deque>
#include <utility>
typedef long long int64;
static const int64 INF = 1LL << 61;
static const int MAXN = 3e5 + 4;
static const int MAXM = 3e5 + 3;

template <typename T> inline T cross(const std::pair<T, T> a, const std::pair<T, T> b, const std::pair<T, T> c) {
    return (c.first - a.first) * (b.second - a.second) - (b.first - a.first) * (c.second - a.second);
}

struct convex_hull {

std::deque<std::pair<int64, int64>> q;

inline void clear() { q.clear(); }

inline void append(std::pair<int64, int64> p) {
    while (q.size() >= 2u && cross(p, q[0], q[1]) >= 0) q.pop_front();
    q.push_front(p);
}
inline void append(int64 x, int64 y) { this->append(std::make_pair(x, y)); }

inline int64 query(int64 slope) {
    int lo = 0, hi = q.size(), mid;
    while (lo < hi - 1) {
        mid = (lo + hi) >> 1;
        if (q[mid].second - q[mid].first * slope >= q[mid - 1].second - q[mid - 1].first * slope)
            lo = mid;
        else hi = mid;
    }
    return q[lo].second - q[lo].first * slope;
}

};

int n, t[MAXN];
int m, p, x;

int64 glob_l[MAXN], glob_r[MAXN];
int64 inc[MAXN], exc[MAXN];
int64 pfx[MAXN];

void calc_global(int64 *f)
{
    static int64 pfx[MAXN];
    pfx[0] = 0;
    for (int i = 1; i <= n; ++i) pfx[i] = pfx[i - 1] + ::t[i];

    convex_hull hull;
    for (int i = 0; i <= n; ++i) {
        if (i == 0) f[i] = 0;
        else f[i] = std::max(f[i - 1], hull.query(i) + (int64)i * (i + 1) - pfx[i] * 2);
        hull.append(i * 2, (int64)i * (i - 1) + pfx[i] * 2 + f[i]);
    }
}

void divide(int l, int r)
{
    if (l > r) return;
    int m = (l + r) >> 1;
    inc[m] = std::max(inc[m], (-t[m] + 1) * 2 + exc[m]);
    if (l == r) return;

    convex_hull h;
    static int64 f[MAXN];

    /*for (int i = l; i <= r; ++i) f[i] = -INF;
    for (int i = l; i <= m; ++i)
        for (int j = m + 1; j <= r; ++j) {
            printf("%d %d %lld\n", i, j, (int64)(j - i + 1) * (j - i + 2));
            f[i] = std::max(f[i], (int64)(j - i + 1) * (j - i + 2) + glob_l[i - 1] + glob_r[j] - pfx[j] * 2 + pfx[i - 1] * 2);
            f[j] = std::max(f[j], (int64)(j - i + 1) * (j - i + 2) + glob_l[i - 1] + glob_r[j] - pfx[j] * 2 + pfx[i - 1] * 2);
        }*/

    // [L, M] -> (M, R]
    for (int i = l; i <= r; ++i) {
        if (i <= m) h.append(i * 2, (int64)i * (i - 3) + pfx[i - 1] * 2 + glob_l[i - 1]);
        else f[i] = h.query(i) + (int64)i * (i + 3) - pfx[i] * 2 + glob_r[i] + 2;
    }
    // [L, M] <- (M, R]
    h.clear();
    for (int i = m + 1; i <= r; ++i)
        h.append(i * 2, (int64)i * (i + 3) - pfx[i] * 2 + glob_r[i]);
    for (int i = l; i <= m; ++i) f[i] = h.query(i) + (int64)i * (i - 3) + pfx[i - 1] * 2 + glob_l[i - 1] + 2;

    int64 max = -INF;
    for (int i = r; i > m; --i) {
        max = std::max(max, f[i]);
        inc[i] = std::max(inc[i], max);
    }
    max = -INF;
    for (int i = l; i <= m; ++i) {
        max = std::max(max, f[i]);
        inc[i] = std::max(inc[i], max);
    }

    divide(l, m - 1);
    divide(m + 1, r);
}

int main()
{
    scanf("%d", &n);
    // Let's use 1-based indices for now ;)
    for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);

    calc_global(glob_l);
    std::reverse(t + 1, t + n + 1);
    calc_global(glob_r);
    std::reverse(glob_r, glob_r + n + 1);
    std::reverse(t + 1, t + n + 1);

    for (int i = 1; i <= n; ++i) exc[i] = glob_l[i - 1] + glob_r[i];
    pfx[0] = 0; for (int i = 1; i <= n; ++i) pfx[i] = pfx[i - 1] + t[i];
    std::fill(inc + 1, inc + n + 1, -INF);
    divide(1, n);

    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &p, &x); //--p;
        printf("%lld\n", std::max(exc[p] / 2, inc[p] / 2 + t[p] - x));
    }

    return 0;
}


Measured memory_bytes: 20224