#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#define ll long long
#define db double
#define TI 1.0 * (clock() - start) / CLOCKS_PER_SEC

using namespace std;

const int MAXN = 300010;
const ll INF = 1e16;

inline int read()
{
    char ch;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) 1;
    int x = ch - '0';
    for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return x;
}

int n, m;
int stk[MAXN], top = 0;
ll a[MAXN], sum[MAXN], dp[MAXN], h[MAXN], tmp[MAXN];
ll fo[MAXN], ba[MAXN], chose_ans[MAXN];//fo forward; ba backward

inline db getK(const int &a, const int &b)
{
	return 1.0 * (dp[a] + sum[a] + 1ll * a * (a - 1) / 2 - dp[b] - sum[b] - 1ll * b * (b - 1) / 2) / (a - b);
}

void getsum()
{
	sum[0] = 0;
	for (int i = 1; i <= n; i++)
		sum[i] = a[i] + sum[i - 1];
}

void getdp()
{
	getsum();
	stk[top = 1] = 0;
	for (int i = 1; i <= n; i++)
	{
		while (top > 1 && getK(stk[top], stk[top - 1]) <= i) top--;
		int now = stk[top];
		dp[i] = max(dp[i - 1], dp[now] + 1ll * (i - now) * (i - now + 1) / 2 + sum[now] - sum[i]);
		while (top > 1 && getK(stk[top], stk[top - 1]) < getK(i, stk[top])) top--;
		stk[++top] = i;
	}
}

void rev()
{
	for (int i = 1; i <= n / 2; i++)
		swap(a[i], a[n - i + 1]);
}

void solve(int l, int r)
{
	if (l == r)
	{
		h[l] = max(h[l], fo[l - 1] + 1 + ba[l + 1] - a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	stk[top = 1] = l - 1;
	for (int i = l; i <= mid - 1; i++)
	{
		while (top > 1 && getK(stk[top], stk[top - 1]) < getK(i, stk[top])) top--;
		stk[++top] = i;
	}
	for (int i = mid; i <= r; i++)
	{
		while (top > 1 && getK(stk[top], stk[top - 1]) <= i) top--;
		int now = stk[top];
		tmp[i] = dp[now] + (i - now) * (i - now + 1) / 2 + sum[now] - sum[i] + ba[i + 1];
	}
	for (int i = r - 1; i >= mid; i--) tmp[i] = max(tmp[i], tmp[i + 1]);
	for (int i = mid; i <= r; i++) h[i] = max(h[i], tmp[i]);
	solve(l, mid); solve(mid + 1, r);
}

int main()
{
	ios::sync_with_stdio(false);
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	
//	int start = clock();
	n = read();
	for (int i = 1; i <= n; i++)
		a[i] = read();
//	cerr << "cin: " << TI << "s" << endl;
//	start = clock();
	
	getdp();
	for (int i = 1; i <= n; i++) fo[i] = dp[i];
	rev();
	
	getdp();
	for (int i = 1; i <= n; i++) ba[n - i + 1] = dp[i];
	rev();
	
//	cerr << "DP: " << TI << "s" << endl;
//	start = clock();
	
	for (int i = 1; i <= n; i++) chose_ans[i] = -INF;
	
	for (int i = 1; i <= n; i++) dp[i] = fo[i];
	getsum();
	for (int i = 1; i <= n; i++) h[i] = -INF;
	solve(1, n);
	for (int i = 1; i <= n; i++)
		chose_ans[i] = max(chose_ans[i], h[i]);
	
	rev();
	for (int i = 1; i <= n; i++) swap(fo[i], ba[i]);
	for (int i = 1; i <= n / 2; i++)
	{
		swap(fo[i], fo[n - i + 1]);
		swap(ba[i], ba[n - i + 1]);
	}
	for (int i = 1; i <= n; i++) dp[i] = fo[i];
	getsum();
	for (int i = 1; i <= n; i++) h[i] = -INF;
	solve(1, n);
	for (int i = 1; i <= n; i++)
		chose_ans[i] = max(chose_ans[i], h[n - i + 1]);
	
	rev();
	for (int i = 1; i <= n; i++) swap(fo[i], ba[i]);
	for (int i = 1; i <= n / 2; i++)
	{
		swap(fo[i], fo[n - i + 1]);
		swap(ba[i], ba[n - i + 1]);
	}
	
//	cerr << "CDQ: " << TI << "s" << endl;
//	start = clock();
	
	m = read();
	while (m--)
	{
		int p, x;
		p = read(), x = read();
		printf("%lld\n", max(fo[p - 1] + ba[p + 1], chose_ans[p] + a[p] - x));
	}
//	cerr << "Query: " << TI << "s" << endl;
	return 0;
}


Measured memory_bytes: 21376