// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// CHT<a-increasing, T, x-increasing?, is-minimize?>
// - maximize : let Comp = greater<T>
// .add(a, b, id?) : f(x) = ax + b
// .query(x)
// .get(x) : line
// line.a, line.b, line.id
// line.calc(x)
/// --- Convex Hull Trick Library {{{ ///
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
template < bool aIncreasing, class T = long long, int xType = 0, bool isMinimize = true,
           class D = T >
struct CHT {
  static_assert(xType == 0 || xType == 1 || xType == -1, "xType must be in {0, +1, -1}");
  static T EPS;
  constexpr static bool headIncreasing = aIncreasing ^ (xType == -1) ^ isMinimize;

private:
  // a is better
  static inline bool comp(const T &a, const T &b) {
    if(isMinimize)
      return a < b;
    else
      return a > b;
  }

  static inline bool comp2(const D &a, const D &b) {
    if(isMinimize ^ aIncreasing)
      return a < b;
    else
      return a > b;
  }

  struct Line {
    T a, b;
    int id;
    Line(T a, T b, int id = 0) : a(a), b(b), id(id) {}
    T calc(const T &x) { return x * a + b; }
    friend ostream& operator<<(ostream & os, Line line) {
      os << "(" << line.a << ", " << line.b << ")";
      return os;
    }
  };

public:
  vector< Line > lines;
  // is l2 unnecessary ?
  bool check(Line l1, Line l2, Line l3) {
    if(l2.a == l3.a) return 1;
    // cp(l2, l3).x <= cp(l2, l1).x
    return !comp2(
        (D)(l2.a - l1.a) * (l3.b - l2.b) + D(EPS), (D)(l3.a - l2.a) * (l2.b - l1.b));
  }

  T f(int i, const T &x) { return lines[i].a * x + lines[i].b; }
  void add(const T &a, const T &b, int id = 0) {
    if(aIncreasing) {
      assert("add a-asc" && (lines.empty() || !(a < lines.back().a)));
    } else {
      assert("add a-desc" && (lines.empty() || !(lines.back().a < a)));
    }
    if(lines.size() && lines.back().a == a && !comp(b, lines.back().b)) return;
    Line line(a, b, id);
    while((int) lines.size() >= 2 && check(lines[lines.size() - 2], lines.back(), line)) {
      lines.pop_back();
      if(!headIncreasing)
        if(head > 0) head--;
    }
    lines.push_back(line);
  }
  T query(const T &x) { return get(x).calc(x); }

private:
  size_t head = 0;
  bool used = false;
  T last;

public:
  Line get(const T &x) {
    assert(lines.size());
    if(xType == 0) {
      int ok = lines.size() - 1, ng = -1;
      while(ok - ng > 1) {
        int mid = (ok + ng) >> 1;
        if(comp(f(mid, x), f(mid + 1, x)))
          ok = mid;
        else
          ng = mid;
      }
      return lines[ok];
    } else if(xType == 1) {
      assert("query increasingly!" && (!used || !(x < last)));
    } else if(xType == -1) {
      assert("query decreasingly!" && (!used || !(last < x)));
    }
    used = true;
    last = x;
    if(head >= lines.size()) head = lines.size() - 1;
    if(headIncreasing) {
      while(head + 1 < lines.size() && comp(f(head + 1, x), f(head, x))) head++;
      return lines[head];
    } else {
      while(head + 1 < lines.size() &&
            comp(f(lines.size() - 1 - (head + 1), x), f(lines.size() - 1 - head, x)))
        head++;
      return lines[lines.size() - 1 - head];
    }
  }
  void clear() {
    head = 0;
    used = false;
    lines.clear();
  }
  friend ostream &operator<<(ostream &os, CHT cht) {
    os << "CHT[";
    os << "a-" << (aIncreasing ? "asc" : "desc") << "; ";
    os << "x-" << (xType != 0 ? xType == -1 ? "desc" : "asc" : "random") << "; ";
    os << (isMinimize ? "min" : "max") << "; ";
    os << "internal-head-" << (headIncreasing ? "asc" : "desc");
    os << "]\n";
    os << cht.lines.size() << " lines\n";
    for(auto &p : cht.lines) os << p << "\n";
    return os;
  }
};

template < bool aIncreasing, class T, int xType, bool isMinimize, class D >
T CHT< aIncreasing, T, xType, isMinimize, D >::EPS = 1e-19;

/// }}}--- ///

// smin, smax {{{
// clang-format off
template < class T, class U > inline void smin(T &a, const U &b) { a = a < (T) b ? a : b; }
template < class T, class U > inline void smax(T &a, const U &b) { a = a < (T) b ? b : a; }
// clang-format on
// }}}

// accum1D, range1D, range1Dloop {{{
#include <vector>
template < class T >
void accum1D(T &a, int n) {
  for(int i = 1; i < n; i++) a[i] += a[i - 1];
}
template < class T >
void accum1D(vector< T > &a) {
  accum1D(a, a.size());
}
template < class T, int N >
void accum1D(T a[N]) {
  accum1D(a, N);
}

template < class T >
auto range1D(const T &a, int l, int r, int n) {
  if(r >= n) r = n - 1;
  auto res(a[r]);
  if(l - 1 >= 0) res -= a[l - 1];
  return res;
}
template < class T >
auto range1D(vector< T > &a, int l, int r) {
  return range1D(a, l, r, a.size());
}
template < class T, int N >
auto range1D(T a[N], int l, int r) {
  return range1D(a, l, r, N);
}

template < class T >
auto range1Dloop(const T &a, ll tl, ll r, int n) {
  decltype(a[0]) res(0);
  if(tl > r) return res;
  assert(n >= 1);
  ll l = tl % n;
  if(l < 0) l += n;
  r += l - tl;
  ll gr = r / n;
  if(gr == 0) {
    res += range1D< T >(a, l, r, n);
  } else {
    res += range1D< T >(a, l, n - 1, n);
    res += range1D< T >(a, 0, r % n, n);
    res += range1D< T >(a, 0, n - 1, n) * (gr - 1);
  }
  return res;
}
template < class T >
T range1Dloop(vector< T > &a, ll l, ll r) {
  return range1Dloop(a, l, r, a.size());
}
template < class T, int N >
T range1Dloop(T a[N], ll l, ll r) {
  return range1Dloop(a, l, r, N);
}
// }}}

constexpr int N = 3e5 + 10;

ll useBest[N];
ll notUseBest[N];
ll t[N], trev[N];
ll tsum[N], trevsum[N];

int n, q;

// [l, r]
template < class T >
auto _calc(int l, int r, T &tsum) {
  assert(1 <= l && l <= r && r <= n);
  int m = r - l + 1;
  vector< ll > d(m + 1);
  vector< ll > d2(m + 1);
  CHT< false, ll, true, false > cht;

  cht.add(1, 0);
  for(ll i = 1; i <= m; i++) {
    d2[i] = (cht.query(i) + i * i - 2 * range1D(tsum, l - 1, l - 1 + i, n + 1)) / 2;
    d[i] = max(d[i - 1], d2[i]);
    cht.add(1 - 2 * i, 2 * d[i] + i * i - i + 2 * range1D(tsum, l - 1, l - 1 + i, n + 1));
  }
  return make_pair(d, d2);
}

auto calc(int l, int r) { return _calc(l, r, tsum); }

auto calcrev(int l, int r) {
  l = n + 1 - l;
  r = n + 1 - r;
  auto p = _calc(r, l, trevsum);
  p.first.push_back(0);
  p.second.push_back(0);
  reverse(begin(p.first), end(p.first));
  reverse(begin(p.second), end(p.second));
  return p;
}

vector< ll > l2r;
vector< ll > r2l;
vector< ll > r2l_orig;

// [l, r]
template < class T, class U >
auto _calc(int l, int r, T &tsum, U &u, int cover) {
  assert(1 <= l && l <= r && r <= n && l <= cover && cover <= r);
  int m = r - l + 1;
  vector< ll > d(m + 1);
  vector< ll > d2(m + 1);
  CHT< false, ll, true, false > cht;

  for(int x = l - 1; x < cover; x++) {
    ll i = x - (l - 1);
    cht.add(1 - 2 * i, 2 * u[x] + i * i - i + 2 * range1D(tsum, l - 1, l - 1 + i, n + 1));
  }
  for(ll i = cover - (l - 1); i <= m; i++) {
    d[i] = (cht.query(i) + i * i - 2 * range1D(tsum, l - 1, l - 1 + i, n + 1)) / 2;
  }
  return make_pair(d, d2);
}

auto calc(int l, int r, int m) { return _calc(l, r, tsum, l2r, m); }

auto calcrev(int l, int r, int m) {
  l = n + 1 - l;
  r = n + 1 - r;
  m = n + 1 - m;
  auto p = _calc(r, l, trevsum, r2l_orig, m);
  p.first.push_back(0);
  p.second.push_back(0);
  reverse(begin(p.first), end(p.first));
  reverse(begin(p.second), end(p.second));
  return p;
}

// [l, r]
void dac(int l, int r) {
  if(l >= r + 1) return;
  int m = (l + r) >> 1;
  dac(l, m - 1);
  dac(m + 1, r);
  int len = r - l + 1;
  // 範囲内の各iについて，"mを覆う区間によって利用される" と言うような場合の最大スコア
  // dump(l, r);
  auto l2r_B = calc(l, r, m).first;
  auto r2l_B = calcrev(l, r, m).first;
  // dump(l2r_B);
  // dump(r2l_B);

  vector< ll > ub(len);

  for(int i = m; i <= r; i++) {
    ll val = l2r_B.at(-l + 1 + i);
    if(i + 1 <= n) val += r2l.at(i + 1); // global
    ub.at(i - l) = val;
  }
  // dump(ub);
  for(int i = l; i <= m; i++) {
    ll val = r2l_B.at(-l + 1 + i);
    if(i - 1 >= 1) val += l2r.at(i - 1); // global
    if(i == m)
      smax(ub.at(i - l), val);
    else
      ub.at(i - l) = val;
  }
  for(int i = r - 1; i >= m; i--) smax(ub.at(-l + i), ub.at(-l + i + 1));
  for(int i = l + 1; i <= m; i++) smax(ub.at(-l + i), ub.at(-l + i - 1));
  // dump(ub);
  for(int i = 0; i < len; i++) smax(useBest[l + i], ub.at(i));
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> t[i];
  copy(t + 1, t + 1 + n, tsum + 1);
  copy(t + 1, t + 1 + n, trev + 1);
  reverse(trev + 1, trev + 1 + n);
  copy(trev + 1, trev + 1 + n, trevsum + 1);
  accum1D(tsum, n + 1);
  accum1D(trevsum, n + 1);

  l2r = calc(1, n).first;
  r2l_orig = r2l = calcrev(1, n).first;
  reverse(begin(r2l_orig), end(r2l_orig));

  for(int i = 1; i <= n; i++) {
    useBest[i] = -1e18;
    if(i - 1 >= 1) notUseBest[i] += l2r[i - 1];
    if(i + 1 <= n) notUseBest[i] += r2l[i + 1];
  }

  dac(1, n);

  // dump1D(useBest, n + 1);
  // dump1D(notUseBest, n + 1);

  cin >> q;

  for(int i = 0; i < q; i++) {
    int p, x;
    cin >> p >> x;
    cout << max(useBest[p] - x + t[p], notUseBest[p]) << "\n";
  }
  return 0;
}


Measured memory_bytes: 40172