#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int N;
long long dp[maxn];
long long p[maxn];
int T[maxn];
long long pre[maxn], suf[maxn];
const long long inf = 1e17;
long long nc2(long long x) {
    return (x * (x - 1)) / 2;
}

// m1 x + c1 = m2 x + c2
// x (m1 - m2) = (c2 - c1)
// x = (c2 - c1) / (m1 - m2)
// x(j, k) <= x(i, k)

struct Hull {
  vector <long long> M, C;
  int pt = 0;
  Hull() {}
  bool bad(int i, int j, int k) {
    return (C[j] - C[k]) * (M[k] - M[i]) <= (C[i] - C[k]) * (M[k] - M[j]);
  }
  void add_line(long long m, long long c) {
    M.emplace_back(m);
    C.emplace_back(c);
    while(M.size() > 2 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
      M.erase(M.end() - 2);
      C.erase(C.end() - 2);
    }
  }
  long long query(long long x) {
    while(pt + 1 < M.size() && M[pt] * x + C[pt] <= M[pt + 1] * x + C[pt + 1]) {
      ++pt;
    }
    return M[pt] * x + C[pt];
  }
  long long eval(long long x) {
    int l = 0, r = M.size() - 1;
    while(l < r) {
      int mid = (l + r) >> 1;
      if(M[mid] * x + C[mid] <= M[mid + 1] * x + C[mid + 1]) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    return M[l] * x + C[l];
  }
};

long long calcPrefix() {
    for(int i = 1; i <= N; i++) {
        p[i] = p[i - 1] + T[i];
    }
    Hull H;
    H.add_line(0, 0);
    for(int i = 1; i <= N; i++) {
        dp[i] = dp[i - 1];
        dp[i] = max(dp[i], H.eval(-i) - p[i] + (1LL * i * (i + 1)) / 2);
        H.add_line(i, dp[i] + p[i] + (1LL * i * (i - 1)) / 2);
    }
    return dp[N];
}

// (i - j + 1)(i - j) = (i^2 - 2ij + j^2 + i - j) = (i^2 + i + j^2 - j + 2ij)
// C(i - j + 1, 2) = (i^2 + i) / 2 + {dp[j] + (j^2 - j) / 2} - ij

long long inc[maxn];
long long aux[maxn];

void solve(int l, int r) {
  if(l == r) return ;
  int m = (l + r) >> 1;
  Hull H, I;
  H.add_line(0, suf[m]);
  I.add_line(0, pre[m + 1]);
  for(int i = m + 1; i <= r; i++) {
    int sz = i - m;
    H.add_line(sz, nc2(sz + 1) + p[m] - p[i] + suf[i + 1]);
  }
  for(int i = m; i >= l; i--) {
    int sz = m - i + 1;
    I.add_line(sz, nc2(sz + 1) + p[i - 1] - p[m] + pre[i - 1]);
  }
  for(int i = m; i >= l; i--) {
    int sz = m - i + 1;
    aux[i] = H.query(sz) + nc2(sz + 1) + p[i - 1] - p[m] + pre[i - 1];
  }
  for(int i = m + 1; i <= r; i++) {
    int sz = i - m;
    aux[i] = I.query(sz) + nc2(sz + 1) + p[m] - p[i] + suf[i + 1];
  }
  long long var = -inf;
  for(int i = r; i > m; i--) {
    var = max(var, aux[i]);
    inc[i] = max(inc[i], var);
  }
  var = -inf;
  for(int i = l; i <= m; i++) {
    var = max(var, aux[i]);
    inc[i] = max(inc[i], var);
  }
  solve(l, m);
  solve(m + 1, r);
}
int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) {
		scanf("%d", &T[i]);
	}
  calcPrefix();
  for(int i = 1; i <= N; i++) {
    pre[i] = dp[i];
  }
  reverse(T + 1, T + N + 1);
  calcPrefix();
  reverse(dp + 1, dp + N + 1);
  for(int i = 1; i <= N; i++) {
    suf[i] = dp[i];
  }
  reverse(T + 1, T + N + 1);
  for(int i = 1; i <= N; i++) p[i] = p[i - 1] + T[i];
  for(int i = 1; i <= N; i++) inc[i] = -inf;
  solve(1, N);
  int M;
  scanf("%d", &M);
  for(int cs = 1; cs <= M; cs++) {
    int p, x;
    scanf("%d %d", &p, &x);
    long long ans = inc[p] - x + T[p];
    ans = max(ans, pre[p - 1] + suf[p + 1]);
    printf("%lld\n", ans);
  }

  return 0;
}	


Measured memory_bytes: 17792