#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
using ll = long long;
int n, m, w[N], q[N], h, t;
ll f[N], g[N], fy[N], gy[N], fT[N], ans[N], gT[N], dw[N];
template <class T>
void Max(T &x, T y) {
  if (x < y) x = y;
}
void Solve(int l, int r) {
  if (r == l) return Max(ans[l], f[l - 1] + g[l + 1] + 1 - w[l]);
  int mid = (l + r) >> 1;
  ll j;
  h = 1;
  t = 0;
  for (int i = l; i <= mid; ++i) {
    while (h < t && (fy[i] - fy[q[t]]) * (q[t] - q[t - 1]) <
                        (fy[q[t]] - fy[q[t - 1]]) * (i - q[t]))
      --t;
    q[++t] = i;
  }
  for (int i = mid + 1; i <= r; ++i) {
    while (h < t && (fy[q[h + 1]] - fy[q[h]]) > 2ll * i * (q[h + 1] - q[h]))
      ++h;
    j = fy[q[h]] - 2ll * i * q[h];
    (j += 1ll * i * i - fT[i] * 2 - i) >>= 1;
    dw[i] = j + g[i + 1];
  }
  for (int i = r; i > mid; --i) {
    if (i < min(n, r)) Max(dw[i], dw[i + 1]);
    Max(ans[i], dw[i]);
  }
  h = 1;
  t = 0;
  for (int i = r; i > mid; --i) {
    while (h < t && (gy[i] - gy[q[t]]) * (q[t] - q[t - 1]) <
                        (gy[q[t]] - gy[q[t - 1]]) * (i - q[t]))
      --t;
    q[++t] = i;
  }
  for (int i = l; i <= mid; ++i) {
    while (h < t &&
           (gy[q[h + 1]] - gy[q[h]]) > 2ll * (n + 1 - i) * (q[h] - q[h + 1]))
      ++h;
    j = gy[q[h]] - 2ll * (n + 1 - i) * (n + 1 - q[h]);
    (j += 1ll * (n + 1 - i) * (n + 1 - i) - gT[i] * 2 - (n + 1 - i)) >>= 1;
    dw[i] = j + f[i - 1];
  }
  for (int i = l; i <= mid; ++i) {
    if (i > max(1, l)) Max(dw[i], dw[i - 1]);
    Max(ans[i], dw[i]);
  }
  Solve(l, mid);
  Solve(mid + 1, r);
}
void Dp(ll *f, ll *y, ll *T) {
  for (int i = 1; i <= n; ++i) T[i] = T[i - 1] - 1 + w[i];
  q[h = t = 1] = 0;
  for (int i = 1; i <= n; ++i) {
    f[i] = -1e18;
    while (h < t && (y[q[h + 1]] - y[q[h]]) > 2ll * i * (q[h + 1] - q[h])) ++h;
    f[i] = y[q[h]] - 2ll * i * q[h];
    (f[i] += 1ll * i * i - T[i] * 2 - i) >>= 1;
    Max(f[i], f[i - 1]);
    y[i] = f[i] * 2 + 1ll * i * i + i + T[i] * 2;
    while (h < t && (y[i] - y[q[t]]) * (q[t] - q[t - 1]) >
                        (y[q[t]] - y[q[t - 1]]) * (i - q[t]))
      --t;
    q[++t] = i;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
  memset(ans, 0xc0, sizeof ans);
  Dp(f, fy, fT);
  reverse(w + 1, w + n + 1);
  Dp(g, gy, gT);
  reverse(w + 1, w + n + 1);
  reverse(gy + 1, gy + n + 1);
  reverse(g + 1, g + n + 1);
  reverse(gT + 1, gT + n + 1);
  Solve(0, n + 1);
  scanf("%d", &m);
  for (int i = 1, p, x; i <= m; ++i) {
    scanf("%d%d", &p, &x);
    printf("%lld\n", max(ans[p] + w[p] - x, f[p - 1] + g[p + 1]));
  }
  return 0;
}
