// Slower C++ solution:
#include<bits/stdc++.h>

#include<deque>

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long





const int maxn = 3e5 + 5;

int n, m;

ll t[maxn], p[maxn], f[maxn], g[maxn], F[maxn], G[maxn], h[maxn];

pair<int, ll> drink[maxn];

struct node

{

	ll x, y;

};

double k(const node &a, const node &b)

{

	return double(a.y - b.y) / double(a.x - b.x);

}

ll crossz(const node &a, const node &b, const node& c)

{

	return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);

}

void rev(ll *a)

{

	for (int i = 1; i <= n - i + 1; ++i)swap(a[i], a[n - i + 1]);

}

void cal(ll *dp)

{

	p[0] = 0;

	for (int i = 1; i <= n; ++i)p[i] = p[i - 1] + t[i];

	deque<node> Q;

	Q.push_back({ 0, 0 });

	dp[0] = 0;

	for (ll i = 1; i <= n; ++i)

	{

		dp[i] = dp[i - 1];

		while (Q.size() > 1)

		{

			node temp = Q.back(); Q.pop_back();

			node temp2 = Q.back();

			ll ans1, ans2;

			ans1 = temp.y - i * temp.x - p[i] + (i*i + i) / 2;

			ans2 = temp2.y - i * temp2.x - p[i] + (i*i + i) / 2;

			if (ans1 > ans2)

			{

				Q.push_back(temp);

				break;

			}

		}

		dp[i] = max(dp[i], Q.back().y - i * Q.back().x - p[i] + (i*i + i) / 2);

		//add dp[i]

		node temp = { i, dp[i] + p[i] + (i * i - i) / 2 };

		while (Q.size() > 1)

		{

			node back = Q.back(); Q.pop_back();

			//用除法求斜率判大小，精度有误差

			double k1 = k(temp, back), k2 = k(back, Q.back());

			if (k1 < k2)

			//if(crossz(Q.back(), back, temp) < 0)

			{

				Q.push_back(back); break;

			}

		}

		Q.push_back(temp);

	}

}



void calh(int l, int r)

{

	if (l == r)

	{

		h[l] = max(h[l], f[l - 1] + g[r + 1] + 1 - t[l]);

		return;

	}

	int mid = (l + r >> 1);

	for (ll i = l; i <= mid; ++i)F[i] = f[i - 1] + p[i - 1] + (i*i - 3 * i) / 2 + 1;

	for (ll j = mid + 1; j <= r; ++j)G[j] = g[j + 1] - p[j] + (j*j + j * 3) / 2;

	deque<node> Q;

	for (int i = mid + 1; i <= r; ++i)

	{

		node now = { i,  G[i] };

		while (Q.size() > 1)

		{

			node tmp = Q.back(); Q.pop_back();

			double k1 = k(now, tmp), k2 = k(tmp, Q.back());

			if(k1 < k2)//if(crossz(Q.back(), tmp, now) < 0)//if (k1 < k2)

			{

				Q.push_back(tmp); break;

			}

		}

		Q.push_back(now);

	}

	ll t = -4e18;

	for (ll j = l; j <= mid; ++j)

	{

		while (Q.size() > 1)

		{

			ll ans1, ans2;

			node tmp = Q.back(); Q.pop_back();

			ans1 = tmp.y - tmp.x * j, ans2 = Q.back().y - Q.back().x * j;

			if (ans1 > ans2)

			{

				Q.push_back(tmp); break;

			}

		}

		t = max(t, Q.back().y - Q.back().x * j + F[j]);

		h[j] = max(t, h[j]);

	}

	calh(l, mid); calh(mid + 1, r);

}



void solve()

{

	cin >> n;

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

	cin >> m;

	//for (int i = 1; i <= m; ++i)cin >> drink[i].first >> drink[i].second;

	memset(h, 0xbf, sizeof(h));//初值不能为0，因为要求i必选，值可能为负

	cal(f);

	rev(t); cal(g);

	rev(t); rev(g);

	for (int i = 1; i <= n; ++i)p[i] = p[i - 1] + t[i];

	calh(1, n);

	rev(t);

	for (int i = 1; i <= n; ++i)p[i] = p[i - 1] + t[i];

	swap(f, g); rev(f); rev(g);

	rev(h);

	calh(1, n);

	rev(t); rev(h); rev(f); rev(g);

	swap(f, g);



	for (int i = 1; i <= m; ++i)

	{

		ll p, v; cin >> p >> v;

		//ll p = drink[i].first, v = drink[i].second;

		ll ans = max(f[p - 1] + g[p + 1], h[p] + t[p] - v);

		cout << ans << "\n";

	}

}

signed main()

{

	ios::sync_with_stdio(false); cin.tie(0);

	//	int t; cin >> t;

	//	for(int i = 1; i <= t; ++i)

	solve();

	//system("pause");

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.959885021948889x):
#include <bits/stdc++.h>

using namespace std; 

const int N = 300010;

typedef long long ll; 

const ll LINF = 1e16; 

int n,m;

ll t[N],sum[N];

ll f[N],g[N],*dp;

int st[N],top;

int read()

{

	int x = 0, w = 1; char c = getchar(); 

	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 

	return x * w; 

}

double X(int j) { return j; }

double Y(int j) { return dp[j] + ((ll)j * j - j) / 2 + sum[j]; }

double slope(int i,int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }

ll calc(int i,int j) { return dp[j] + ((ll)(i - j + 1) * (i - j)) / 2 - (sum[i] - sum[j]); }

void DP()

{

	for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + t[i];

	st[top = 1] = 0;

	for(int i = 1;i <= n;i++)

	{

		while(top > 1 && calc(i,st[top]) <= calc(i,st[top - 1])) top--; 

		dp[i] = max(calc(i,st[top]),dp[i - 1]); 

		while(top > 1 && slope(st[top - 1],i) >= slope(st[top],st[top - 1])) top--;

		st[++top] = i;

	}

}



double X1(int j) { return j; }

double Y1(int j) { return f[j] + sum[j] + ((ll)j * j - j) / 2; }

double slope1(int i,int j) { return (Y1(i) - Y1(j)) / (X1(i) - X1(j)); }

ll calc1(int i,int j)

{ return g[i + 1] + ((ll)(i - j) * (i - j + 1)) / 2 - (sum[i] - sum[j]) + f[j]; }



double X2(int j) { return j; }

double Y2(int j) { return g[j + 1] + ((ll)j * j + j) / 2 - sum[j]; }

double slope2(int i,int j) { return (Y2(i) - Y2(j)) / (X2(i) - X2(j)); }

ll calc2(int i,int j)

{ return f[i] + ((ll)(j - i) * (j - i + 1)) / 2 - (sum[j] - sum[i]) + g[j + 1]; }



ll h[N];

void solve(int l,int r)

{

	if(l == r) { h[l] = 1 - t[l];return; }

	int mid = l + r >> 1;solve(l,mid),solve(mid + 1,r);

	top = 0;

	for(int i = l - 1;i < mid;i++)

	{

		while(top > 1 && slope1(i,st[top - 1]) >= slope1(st[top],st[top - 1])) top--;

		st[++top] = i;

	}int head = 1;ll maxx = -LINF;

	for(int i = r;i > mid;i--)

	{

		while(head < top && calc1(i,st[head]) <= calc1(i,st[head + 1])) head++;

		maxx = max(maxx,calc1(i,st[head]));

		h[i] = max(h[i],maxx);

	}top = 0;

	for(int i = mid + 1;i <= r;i++)

	{

		while(top > 1 && slope2(i,st[top - 1]) >= slope2(st[top],st[top - 1])) top--;

		st[++top] = i;

	}maxx = -LINF;

	for(int i = l - 1;i < mid;i++)

	{

		while(top > 1 && calc2(i,st[top]) <= calc2(i,st[top - 1])) top--;

		maxx = max(maxx,calc2(i,st[top]));

		h[i + 1] = max(h[i + 1],maxx);

	}

}

int main()

{

	n = read();for(int i = 1;i <= n;i++) t[i] = read();

	dp = f,DP();

	reverse(t + 1,t + 1 + n),dp = g,DP();

	reverse(t + 1,t + 1 + n),reverse(g + 1,g + 1 + n); 

	for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + t[i];

	solve(1,n);m = read();

	while(m--)

	{

		int x = read(), y = read();

		printf("%lld\n", max(f[x - 1] + g[x + 1],h[x] + t[x] - y));

	}

	return 0;

}