// 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.880449691583898x):
#include<bits/stdc++.h>

using namespace std;



const int maxn = 3e5 + 10;

const long long inf = 1e18;



int n, m;

long long a[maxn], f[maxn], g[maxn], y[maxn], q[maxn], sum[maxn], h[maxn], temp[maxn];



inline bool check1 (int a, int b, int k) {return y[b] - y[a] < 1LL * (b - a) * k;}

inline bool check2 (int a, int b, int k) {return 1LL * (k - b) * (y[k] - y[a]) - 1LL * (k - a) * (y[k] - y[b]) < 0;}

inline void shift (int a, int b, long long c[]) {c[a] = max (c[a], c[b] + 1LL * (a - b) * (a - b + 1) / 2 - sum[a] + sum[b]);}



void get_dp (long long f[])

{

    int st = 0, ed = 0;

    q[ed++] = 0;

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

    {

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

        for (; st < ed - 1 && check1 (q[ed - 2], q[ed - 1], i); ed--);

        f[i] = f[i - 1];

        shift (i, q[ed - 1], f);

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

        for (; st < ed - 1 && check2 (q[ed - 2], q[ed - 1], i); ed--);

        q[ed++] = i;

    }

}



inline void rev (long long f[]) {for (int i = 1; i <= n / 2; i++) swap(f[i], f[n - i + 1]);}



inline void divide_conquer (long long f[], long long g[], int l, int r)

{

    if (l == r)

    {

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

        return ;

    }

    if (l > r) return;

    int mid = l + r >> 1;

    int st = 0, ed = 0;

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

    {

        for (; st < ed - 1 && check2 (q[ed - 2], q[ed - 1], i); ed--);

        if (i < mid) q[ed++] = i, temp[i] = f[i];

        else

        {

            temp[i] = -inf;

            temp[i] = max(temp[i] , f[q[ed - 1]] + 1LL * (i - q[ed - 1]) * (i - q[ed - 1] + 1) / 2 - sum[i] + sum[q[ed - 1]] + g[i + 1]);

        }

    }

    for (int i = r - 1; i >= mid; i--) temp[i] = max (temp[i], temp[i + 1]);

    for (int i = r; i >= mid; i--) h[i] = max (h[i], temp[i]);



    divide_conquer (f, g, l, mid);

    divide_conquer (f, g, mid + 1, r);

}



int main()

{

    //freopen("C:/Users/MACHENIKE/Desktop/data.in","r",stdin);

    scanf("%d", &n);

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

    scanf("%d", &m);



    rev (a);

    get_dp (g); rev(g);

    rev (a);

    get_dp (f);



    for (int i = 0; i <= n + 1; i++) h[i] = -inf;

    divide_conquer (f, g, 1, n);

    rev(a); rev(g); rev(f); rev(h);

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

    {

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

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

    }

    divide_conquer (g, f, 1, n);

    rev(h); rev(g); rev(f); rev(a);



    while (m--)

    {

        int u, v;

        scanf("%d %d", &u, &v);

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

    }

    return 0;

}