#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const int64 infll = (1LL << 61) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename T >
struct LiChaoTree {
  struct Line {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    inline T get(T x) const { return a * x + b; }

    inline bool over(const Line &b, const T &x) const {
      return get(x) > b.get(x);
    }
  };

  vector< T > xs;
  vector< Line > seg;
  int sz;

  LiChaoTree(const vector< T > &x, T INF) : xs(x) {
    sz = 1;
    while(sz < xs.size()) sz <<= 1;
    while(xs.size() < sz) xs.push_back(xs.back() + 1);
    seg.assign(2 * sz - 1, Line(0, INF));
  }

  void update(Line &x, int k, int l, int r) {
    int mid = (l + r) >> 1;
    auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
    if(malta) swap(seg[k], x);
    if(l + 1 >= r) return;
    else if(latte != malta) update(x, 2 * k + 1, l, mid);
    else update(x, 2 * k + 2, mid, r);
  }

  void update(T a, T b) { // ax+b
    Line l(a, b);
    update(l, 0, 0, sz);
  }

  T query(int k) { // xs[k]
    const T x = xs[k];
    k += sz - 1;
    T ret = seg[k].get(x);
    while(k > 0) {
      k = (k - 1) >> 1;
      ret = max(ret, seg[k].get(x));
    }
    return ret;
  }
};

vector< int64 > solve(vector< int64 > &V) {
  int N = (int) V.size();
  vector< int64 > S(N + 1);
  for(int i = 0; i < N; i++) S[i + 1] = S[i] + V[i];
  for(int i = 0; i <= N; i++) S[i] *= 2;
  vector< int64 > dp(N + 1);
  vector< int64 > v(N);
  iota(begin(v), end(v), 1);
  LiChaoTree< int64 > cht(v, -infll);
  cht.update(0, 0);
  for(int i = 1; i <= N; i++) {
    chmax(dp[i], dp[i - 1]);
    chmax(dp[i], 1LL * i * (i + 1) - S[i] + cht.query(i - 1));
    cht.update(-2 * i, dp[i] + 1LL * i * (i - 1) + S[i]);
  }
  return dp;
}


int64 N, M;
vector< int64 > prefix, suffix;
vector< int64 > S, tap;

void rec(int l, int r) {
  if(l >= r) return;

  int m = (l + r) / 2;

  {
    vector< int64 > v;
    for(int i = r; i > m; i--) v.emplace_back(i);
    sort(begin(v), end(v));
    LiChaoTree< int64 > cht(v, -infll);
    for(int i = l; i <= m; i++) {
      cht.update(-2 * i, prefix[i] + 1LL * i * (i - 1) + S[i]);
    }
    int64 mx = -infll;
    for(int i = r; i > m; i--) {
      chmax(mx, cht.query(lower_bound(begin(v), end(v), i) - begin(v)) + 1LL * i * (i + 1) - S[i] + suffix[i]);
      chmax(tap[i - 1], mx);
    }
  }


  {
    vector< int64 > v;
    for(int i = l; i <= m; i++) v.emplace_back(-i);
    reverse(begin(v), end(v));
    LiChaoTree< int64 > cht(v, -infll);
    for(int i = m + 1; i <= r; i++) {
      cht.update(2 * i, 1LL * i * (i + 1) - S[i] + suffix[i]);
    }
    int64 mx = -infll;
    for(int i = l; i <= m; i++) {
      chmax(mx, cht.query(lower_bound(begin(v), end(v), -i) - begin(v)) + 1LL * i * (i - 1) + S[i] + prefix[i]);
      chmax(tap[i], mx);
    }
  }

  rec(l, m);
  rec(m + 1, r);
}


int main() {
  cin >> N;
  vector< int64 > T(N);
  cin >> T;
  cin >> M;

  prefix = solve(T);
  reverse(begin(T), end(T));
  suffix = solve(T);
  reverse(begin(T), end(T));
  reverse(begin(suffix), end(suffix));
  S.resize(N + 1);
  for(int i = 0; i < N; i++) S[i + 1] = S[i] + T[i];
  for(int i = 0; i <= N; i++) S[i] *= 2;
  tap.assign(N, -infll);
  rec(0, N);
  while(M--) {
    int64 P, X;
    cin >> P >> X;
    --P;
    X *= 2;
    cout << max(prefix[P] + suffix[P + 1], tap[P] + T[P] * 2 - X) / 2 << endl;
  }
}


Measured memory_bytes: 38000