// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=300005;



long long N,T[MAXN];

long long q[MAXN],head,tail;

long long sum[MAXN],y[MAXN];

long long L[MAXN],R[MAXN],f[MAXN],g[MAXN],h[MAXN];



void DP(long long dp[],long long N)

{

	q[head=tail=1]=0;

	y[0]=0;

	for(long long i=1;i<=N;i++)

	{

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail];

			if((y[b]-y[a])<1LL*i*(b-a))

				tail--;

			else

				break;

		}

		long long j=q[tail];

		dp[i]=max(dp[i-1],dp[j]+(i-j)*(i-j-1)/2+(i-j)-sum[i]+sum[j]);

		y[i]=dp[i]+1LL*(i-1)*i/2+sum[i];

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail],c=i;

			if((y[b]-y[a])*(c-b)<1LL*(y[c]-y[b])*(b-a))

				tail--;

			else

				break;

		}

		q[++tail]=i;

	}

}



void CDQ(long long l,long long r,long long mode)

{

	if(l==r)

	{

		f[l]=max(f[l],L[l-1]+R[r+1]+1-T[l]);

		return;

	}

	long long mid=(l+r+mode)/2;

	CDQ(l,mid,mode);

	CDQ(mid+1,r,mode);

	

	q[head=tail=1]=l-1;

	g[l-1]=L[l-1];

	y[l-1]=g[l-1]+(l-1-1)*(l-1)/2+sum[l-1];

	for(long long i=l;i<=mid;i++)

	{

		g[i]=L[i];

		y[i]=g[i]+1LL*(i-1)*i/2+sum[i];

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail],c=i;

			if((y[b]-y[a])*(c-b)<1LL*(y[c]-y[b])*(b-a))

				tail--;

			else

				break;

		}

		q[++tail]=i;

	}

	

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

	{

		while(head<tail)

		{

			long long a=q[tail-1],b=q[tail];

			if((y[b]-y[a])<1LL*i*(b-a))

				tail--;

			else

				break;

		}

		long long j=q[tail];

		g[i]=g[j]+(i-j)*(i-j-1)/2+(i-j)-sum[i]+sum[j]+R[i+1];

	}

	

	for(long long i=r-1;i>mid;i--)

		g[i]=max(g[i],g[i+1]);

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

		f[i]=max(f[i],g[i]);

}



int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	

	scanf("%lld",&N);

	for(long long i=1;i<=N;i++)

		scanf("%lld",&T[i]);

	

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	DP(L,N);

	reverse(T+1,T+N+1);

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	DP(R,N);

	reverse(R+1,R+N+1);



	memset(h,0x80,sizeof h);

	

	for(long long i=1;i<=N;i++)

		swap(L[i],R[N-i+1]);

	

	memset(f,0x80,sizeof f);

	CDQ(1,N,-1);

	for(long long i=1;i<=N;i++)

		h[i]=max(h[i],f[N-i+1]);



	reverse(T+1,T+N+1);

	for(long long i=1;i<=N;i++)

		swap(L[i],R[N-i+1]);

	

	for(long long i=1;i<=N;i++)

		sum[i]=sum[i-1]+T[i];

	

	memset(f,0x80,sizeof f);

	CDQ(1,N,0);

	for(long long i=1;i<=N;i++)

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

	

	long long M,P,X;

	scanf("%lld",&M);

	while(M--)

	{

		scanf("%lld%lld",&P,&X);

		long long ans=max(L[P-1]+R[P+1],h[P]+T[P]-X);

		printf("%lld\n",ans);

	}

	

	return 0;

}


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

using namespace std;

const int N = 600010 ;



typedef long long LL ;



LL f[N] ;

LL g[N] ;

LL o[N] ;

LL s[N] ;

LL tmp[N] ;



int t ;

int n, m ;

int stk[N] ;

int base[N] ;



LL calc(LL x, LL y){

    return (x - y) * (x - y + 1) / 2ll ;

}

LL calc0(LL x, LL y){

    return (x - y) * (x - y - 1) / 2ll ;

}

LL Y(LL x){

    return f[x] + s[x] + (x * x + x) / 2ll ;

}

LL YY(LL x){

    return g[x] + s[x] + (x * x + x) / 2ll ;

}

double slope1(int x, int y){

    return 1.0 * (1.0 * Y(x) - 1.0 * Y(y)) / (1.0 * x - 1.0 * y) ;

}

double slope2(int x, int y){

    return 1.0 * (1.0 * YY(x) - 1.0 * YY(y)) / (1.0 * x - 1.0 * y) ;

}

LL Y2(LL x){

    return f[x] + s[x] + (x * x - x) / 2ll ;

}

LL YY2(LL x){

    return g[x] + s[x] + (x * x - x) / 2ll ;

}

double Slope1(int x, int y){

    return 1.0 * (1.0 * Y2(x) - 1.0 * Y2(y)) / (1.0 * x - 1.0 * y) ;

}

double Slope2(int x, int y){

    return 1.0 * (1.0 * YY2(x) - 1.0 * YY2(y)) / (1.0 * x - 1.0 * y) ;

}

void solve(int l, int r){

    if (l == r)

        return o[l] = max(o[l], f[l - 1] + g[r + 1] + 1 - base[l]), void() ;

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

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

    s[l - 1] = s[r + 1] = 0 ; t = 0 ;

    for (int i = l ; i <= r ; ++ i)

        tmp[i] = -(1ll << 62), s[i] = s[i - 1] + base[i] ;

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

        while (t > 1 && Slope1(stk[t], stk[t - 1]) <= Slope1(i, stk[t])) t--;

        stk[++ t] = i ;

    }

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

        while (t > 1 && Slope1(stk[t], stk[t - 1]) <= i) t--;

        tmp[i] = f[stk[t]] + calc(i, stk[t]) - s[i] + s[stk[t]] + g[i + 1] ;

    }

    ans = -(1ll << 62) ;

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

        ans = max(ans, tmp[i]), o[i] = max(o[i], ans) ;

    t = 0 ;

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

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

        while (t > 1 && Slope2(stk[t], stk[t - 1]) >= Slope2(i, stk[t])) t--;

        stk[++ t] = i ;

    }

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

        while (t > 1 && Slope2(stk[t], stk[t - 1]) >= i) t--;

        tmp[i] = g[stk[t]] + calc(stk[t], i) - s[i] + s[stk[t]] + f[i - 1] ;

    }

    ans = -(1ll << 62) ;

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

        ans = max(ans, tmp[i]), o[i] = max(o[i], ans) ;

}

int main(){

    cin >> n ;

    t = 0 ; int p, x ;

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

        scanf("%d", &base[i]),

        o[i] = - (1ll  <<  62),

        s[i] = s[i - 1] + base[i] ;

    }

    stk[++ t] = 0 ; s[n + 1] = s[n] ;

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

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

        f[i] = max(f[i - 1], f[stk[t]] + calc0(i, stk[t]) - s[i - 1] + s[stk[t]]) ;

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

        stk[++ t] = i ;

    }

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

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

    t = 0 ; stk[++ t] = 0 ;

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

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

        g[i] = max(g[i - 1], g[stk[t]] + calc0(i, stk[t]) - s[i - 1] + s[stk[t]]) ;

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

        stk[++ t] = i ;

    }

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

    g[0] = g[n + 1], g[n + 1] = 0 ;

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

    solve(1, n) ; cin >> m ;

    while (m --){

        scanf("%d%d", &p, &x) ;

        printf("%lld\n", max(f[p] + g[p], o[p] + base[p] - x)) ;

    }

    return 0 ;

}