#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<vector>

using namespace std;

#define bomb exit(1)
#define INF 1061109567
#define LINF 4557430888798830399ll
#define pprint(x) print(x),putchar(' ')
#define fprint(x) print(x),putchar('\n')
#define EE(x); struct edge { int nxt,to;ll w; }e[M << 1]; int head[N],ecnt = 1;\
	void add(int u,int v,ll w = 0) { e[++ecnt].w = w,e[ecnt].to = v,e[ecnt].nxt = head[u];head[u] = ecnt; }\
	void add_edge(int u,int v,ll w = 0) { add(u,v,w),add(v,u,w * x); }
#define ll long long
int mod = 1000000007;
ll Mod(ll x) { return x >= mod ? x - mod : x; }
#define eps 0.0000000001
#define sqr(x) ((x) * (x))
#define iter iterator
#define fi first
#define se second
//#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
//char BB[1 << 15],*SS = BB,*TT = BB;
ll read()
{
	ll x = 0;int f = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = -1;
	for(;isdigit(ch);ch = getchar()) x = x * 10 + (ch ^ 48);
	return x * f;
}
void print(ll x)
{
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) print(x / 10);putchar(x % 10 + '0');
}

const int N = 300010;
int n,m;ll t[N],sum[N];
ll f[N],g[N],*dp;
int st[N],top;
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();
		fprint(max(f[x - 1] + g[x + 1],h[x] + t[x] - y));
	}
	return 0;
}

Measured memory_bytes: 15488