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

#define reg register

typedef long long ll;

using namespace std;

const int MN=3e5+5;

int n,m,a[MN];

ll s[MN],f[MN],g[MN];

inline ll Y1(int i){return f[i]+s[i]+1ll*i*(i+1)/2;}

inline ll Y2(int i){return g[i]+s[i]+1ll*i*(i+1)/2;}

inline ll Y3(int i){return f[i]+s[i]+1ll*i*(i-1)/2;}

inline ll Y4(int i){return g[i]+s[i]+1ll*i*(i-1)/2;}

inline double slope1(int i,int j){

	return 1.*(Y1(i)-Y1(j))/(1.*(i-j));

}

inline double slope2(int i,int j){

	return 1.*(Y2(i)-Y2(j))/(1.*(i-j));

}

inline double slope3(int i,int j){

	return 1.*(Y3(i)-Y3(j))/(1.*(i-j));

}

inline double slope4(int i,int j){

	return 1.*(Y4(i)-Y4(j))/(1.*(i-j));

}

int stk[MN],top;

#define mid (l+r>>1)

ll h[MN],t[MN];

void solve(int l,int r){

	if(l==r){h[l]=max(h[l],f[l-1]+g[l+1]+1-a[l]);return;}

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

	s[l-1]=top=0;

	for(reg int i=l;i<=r;i++)s[i]=s[i-1]+a[i];

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

		while(top>1&&slope3(stk[top-1],stk[top])<=slope3(stk[top-1],i))top--;

		stk[++top]=i;

	}

	for(reg int i=mid+1,j;i<=r;i++){

		while(top>1&&slope3(stk[top-1],stk[top])<=i)top--;

		j=stk[top];

		t[i]=f[j]+1ll*(i-j)*(i-j+1)/2-s[i]+s[j]+g[i+1];

	}

	reg ll res=-1e18;

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

		res=max(res,t[i]),h[i]=max(h[i],res);

	s[r+1]=top=0;

	for(reg int i=r;i>=l;i--)s[i]=s[i+1]+a[i];

	for(reg int i=r+1;i>mid+1;i--){

		while(top>1&&slope4(stk[top-1],stk[top])>=slope4(stk[top-1],i))top--;

		stk[++top]=i;

	}

	for(reg int i=mid,j;i>=l;i--){

		while(top>1&&slope4(stk[top-1],stk[top])>=i)top--;

		j=stk[top];

		t[i]=g[j]+1ll*(j-i)*(j-i+1)/2-s[i]+s[j]+f[i-1];

	}

	res=-1e18;

	for(reg int i=l;i<=mid;i++)

		res=max(res,t[i]),h[i]=max(h[i],res);

}

int main(){

	scanf("%d",&n);

	for(reg int i=1;i<=n;i++)scanf("%d",a+i);

	for(reg int i=1;i<=n+1;i++)s[i]=s[i-1]+a[i];

	stk[top=1]=0;

	for(reg int i=1,j;i<=n+1;i++){

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

		j=stk[top];

		f[i]=max(f[i-1],f[j]+1ll*(i-j)*(i-j-1)/2-s[i-1]+s[j]);

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

		stk[++top]=i;

	}

	reverse(a+1,a+1+n);

	for(reg int i=1;i<=n+1;i++)s[i]=s[i-1]+a[i];

	stk[top=1]=0;

	for(reg int i=1,j;i<=n+1;i++){

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

		j=stk[top];

		g[i]=max(g[i-1],g[j]+1ll*(i-j)*(i-j-1)/2-s[i-1]+s[j]);

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

		stk[++top]=i;

	}

	reverse(a+1,a+1+n);

	reverse(g,g+2+n);

	memset(h,~0x3f,sizeof(h));

	solve(1,n);scanf("%d",&m);

	while(m--){

		static int x,y;scanf("%d%d",&x,&y);

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

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.4327878764391397x):
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

const int N = 3e5 + 5; 

typedef long long ll;

const ll INF = 1e16; 

using namespace std;



int n, m, stk[N], top; 

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



template < typename T >

inline T read()

{

	T 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 + s[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 - (s[i] - s[j]); }

void DP()

{

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

	stk[top = 1] = 0;

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

	{

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

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

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

		stk[++top] = i;

	}

}



double X1(int j) { return j; }

double Y1(int j) { return f[j] + s[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 - (s[i] - s[j]) + f[j]; }



double X2(int j) { return j; }

double Y2(int j) { return g[j + 1] + ((ll)j * j + j) / 2 - s[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 - (s[j] - s[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,stk[top - 1]) >= slope1(stk[top],stk[top - 1])) top--;

		stk[++top] = i;

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

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

	{

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

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

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

	}top = 0;

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

	{

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

		stk[++top] = i;

	}maxx = -INF;

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

	{

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

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

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

	}

}

*/



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(stk[top - 1], stk[top]) <= slope1(stk[top - 1], i)) top--; 

		stk[++top] = i; 

	}

	ll mx = -INF, hd = 1; 

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

	{

		while(hd < top && calc1(i, stk[hd]) <= calc1(i, stk[hd + 1])) hd++; 

		j = stk[hd], mx = max(mx, calc1(i, j)); 

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

	}

	top = 0;

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

	{

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

		stk[++top] = i; 

	}

	mx = -INF; 

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

	{

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

		j = stk[top], mx = max(mx, calc2(i, j));		

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

	}

}



int main()

{

	n = read <int> (); 

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

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

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

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

	solve(1, n), m = read <int> (); 

	for(int pos, v, i = 1; i <= m; i++)

	{

		pos = read <int> (), v = read <int> ();

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

	}

	return 0; 

}