#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 300000 + 1000;

int n, m;
int val[MAXN];
long long sum[MAXN], rsum[MAXN];
long long f[MAXN], g[MAXN], h[MAXN];

void work_sum()
{
	for(int i = 1; i <= n; i++)
		sum[i] = val[i] + sum[i - 1];
}

long long get_p(long long *f, int x)
{
	return (long long)x * (x - 1) / 2 + f[x] + sum[x];
}

void dp(long long *f)
{
	static int sta[MAXN];
	int st = 0, ed = 0;
	f[0] = 0;
	sta[ed++] = 0;
	for(int i = 1; i <= n; i++)
	{
		while(ed - st >= 2 && 
			get_p(f, sta[ed - 1]) - get_p(f, sta[ed - 2]) < (long long)i * (sta[ed - 1] - sta[ed - 2]))
			ed--;
		// for(int j = 0; j < ed; j++)
		// 	cerr << sta[j] << ' ';
		// cerr << endl;

		int p = sta[ed - 1];
		f[i] = max(f[i - 1], f[p] + (long long)(i - p) * (i - p + 1) / 2 - sum[i] + sum[p]);

		// long long best = -1e18, pos = -1;
		// for(int j = 0; j <= i - 1; j++)
		// 	if(best < f[j] + (long long)(i - j) * (i - j + 1) / 2 - sum[i] + sum[j])
		// 		best = f[j] + (long long)(i - j) * (i - j + 1) / 2 - sum[i] + sum[j], pos = j;
		// f[i] = max(f[i - 1], best);

		while(ed - st >= 2 && 
			(get_p(f, sta[ed - 1]) - get_p(f, sta[ed - 2])) * (i - sta[ed - 1]) < (get_p(f, i) - get_p(f, sta[ed - 1])) * (sta[ed - 1] - sta[ed - 2]))
			ed--;

		sta[ed++] = i;

		// for(int j = 0; j < ed; j++)
		// 	cerr << sta[j] << ' ';
		// cerr << endl;

		// cerr << i << ' ' << f[i] << "   " << pos << ' ' << p << endl;
	}
	// for(int i = 0; i <= n; i++)
	// 	cerr << i << ' ' << get_p(f, i) << endl;
}

void calc(int l, int mid, int r)
{
	// cerr << l << ' ' << mid << ' ' << r << endl;
	static int sta[MAXN];
	static long long tmp[MAXN];
	int st = 0, ed = 0;
	for(int i = l - 1; i <= mid - 1; i++)
	{
		while(ed - st >= 2 && 
			(get_p(f, sta[ed - 1]) - get_p(f, sta[ed - 2])) * (i - sta[ed - 1]) < (get_p(f, i) - get_p(f, sta[ed - 1])) * (sta[ed - 1] - sta[ed - 2]))
			ed--;
		sta[ed++] = i;
	}
	for(int i = mid + 1; i <= r; i++)
	{
		while(ed - st >= 2 && 
			get_p(f, sta[ed - 1]) - get_p(f, sta[ed - 2]) < (long long)i * (sta[ed - 1] - sta[ed - 2]))
			ed--;
		int j = sta[ed - 1];
		// cerr << i << ' ' << j << endl;
		tmp[i] = f[j] + (long long)(i - j) * (i - j + 1) / 2 - sum[i] + sum[j] + g[i + 1];
	}
	for(int i = r - 1; i >= mid + 1; i--)
		tmp[i] = max(tmp[i], tmp[i + 1]);
	for(int i = mid + 1; i <= r; i++)
		h[i] = max(h[i], tmp[i]);
	// for(int i = mid + 1; i <= r; i++)
	// 	cerr << i << ' ' << tmp[i] << ' ' << h[i] << endl;
}

void solve(int l, int r)
{
	if(l == r)
		return ;
	int mid = (l + r - 1) / 2;
	calc(l, mid, r);
	solve(l, mid);
	solve(mid + 1, r);
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);


	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> val[i];

	work_sum();
	dp(f);

	reverse(val + 1, val + n + 1);
	work_sum();
	dp(g);
	reverse(val + 1, val + n + 1);
	reverse(g + 1, g + n + 1);

	for(int i = 1; i <= n; i++)
		h[i] = f[i - 1] + 1 - val[i] + g[i + 1];

	// for(int i = 1; i <= n; i++)
	// 	cerr << i << ' ' << f[i] << ' ' << g[i] << ' ' << h[i] << endl;

	work_sum();
	solve(1, n);

	reverse(val + 1, val + n + 1);
	reverse(h + 1, h + n + 1);
	for(int i = 1; i <= n; i++)
		swap(f[i], g[n + 1 - i]);
	work_sum();
	solve(1, n);
	reverse(val + 1, val + n + 1);
	reverse(h + 1, h + n + 1);
	for(int i = 1; i <= n; i++)
		swap(f[i], g[n + 1 - i]);

	cin >> m;
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		long long ans = 0;
		ans = max(ans, f[a - 1] + g[a + 1]);
		ans = max(ans, h[a] + val[a] - b);
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 18944