#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 300005;
typedef long long i64;

class Point {
public:
  int id;
  i64 x, y;
  Point(int _id = 0, i64 _x = 0, i64 _y = 0) {
    id = _id, x = _x, y = _y;
  }
  inline friend Point operator + (const Point &a, const Point &b) {
    return Point(0, a.x + b.x, a.y + b.y);
  }
  inline friend Point operator - (const Point &a, const Point &b) {
    return Point(0, a.x - b.x, a.y - b.y);
  }
} ;

i64 cross(Point a, Point b) {
  return a.x * b.y - a.y * b.x;
}
i64 dot(Point a, Point b) {
  return a.x * b.x + a.y * b.y;
}

class Monotonous_Queue {
public:
  int r;
  Point p[MAX_N];
  void init() {
    r = 0;
  }
  void insert(Point x) {
    while (r > 1 && cross(x - p[r - 1], p[r] - p[r - 1]) <= 0) r--;
    p[++r] = x;
  }
  int query(int x) {
    while (r > 1 && p[r].y - p[r - 1].y <= x * (p[r].x - p[r - 1].x)) r--;
    return p[r].id;
  }
} que, que2;

int N, M;

i64 f_front[MAX_N], f_back[MAX_N], sum_front[MAX_N], sum_back[MAX_N];
i64 T[MAX_N], result[MAX_N], temp[MAX_N];

inline i64 calc(int x) {
  return 1LL * x * (x + 1) / 2;
}

void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  
  que.init();
  for (int i = l - 1; i < mid; ++i)
    que.insert(Point(i, i, f_front[i] + sum_front[i] + calc(i - 1)));
  for (int i = mid + 1; i <= r; ++i) {
    int x = que.query(i);
    temp[i] = f_front[x] - sum_front[i] + sum_front[x] + calc(i - x) + f_back[i + 1];
  }
  for (int i = r - 1; i >= mid + 1; --i) 
    temp[i] = max(temp[i + 1], temp[i]);
  for (int i = r; i > mid; --i)
    result[i] = max(result[i], temp[i] + T[i]);
  
  que.init();
  for (int i = r + 1; i > mid + 1; --i) 
    que.insert(Point(i, N - i + 1, f_back[i] + sum_back[i] + calc(N - i)));
  for (int i = mid; i >= l; --i) {
    int x = que.query(N - i + 1);
    temp[i] = f_back[x] - sum_back[i] + sum_back[x] + calc(x - i) + f_front[i - 1];
  }
  
  for (int i = l + 1; i <= mid; ++i) 
    temp[i] = max(temp[i - 1], temp[i]);
  for (int i = l; i <= mid; ++i)
    result[i] = max(result[i], temp[i] + T[i]);
  
  solve(l, mid), solve(mid + 1, r);
}

int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%lld", &T[i]);
    sum_front[i] = sum_front[i - 1] + T[i];
  }
  for (int i = N; i; --i) {
    sum_back[i] = sum_back[i + 1] + T[i];
  }
  
  que.init();
  que.insert(Point(0, 0, 0));
  
  for (int i = 1; i <= N; ++i) {
    int x = que.query(i);
    f_front[i] = f_front[i - 1];
    f_front[i] = max(f_front[i], f_front[x] - sum_front[i] + sum_front[x] + calc(i - x));
    Point p = Point(i, i, f_front[i] + sum_front[i] + calc(i - 1));
    que.insert(p);
  }

  que.init();
  que.insert(Point(N + 1, 0, 0));
  for (int i = N; i; --i) {
    int id = N - i + 1, x = que.query(id);
    f_back[i] = f_back[i + 1];
    f_back[i] = max(f_back[i], f_back[x] - sum_back[i] + sum_back[x] + calc(x - i));
    Point p = Point(i, id, f_back[i] + sum_back[i] + calc(id - 1));
    que.insert(p);
  }

  solve(1, N);

  int M;
  scanf("%d", &M);

  for (int i = 1; i <= M; ++i) {
    int P, X;
    scanf("%d%d", &P, &X);

    i64 res = f_front[P - 1] + f_back[P + 1];
    res = max(res, result[P] - X);
    printf("%lld\n", res);
  }
  
  return 0;
}


Measured memory_bytes: 33024