#include <cstring>
#include <string>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include<iomanip>
using namespace std;
#define ll long long
const int maxn=1e6;
int val[maxn];
ll sum[maxn],f[maxn],dp1[maxn],dp2[maxn],h[maxn],num[maxn];
int sta[maxn],top;
int n,m,p,x;
inline ll F(int x)
{
    if(!x)
    {
        return 0;
    }
    return 2ll*f[x-1]+2ll*sum[x]+1ll*x*x-x;
}
double slope(int x,int y)
{
    return 1.0*(F(y)-F(x))/(y-x);;
}
inline void dp(){
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+val[i];
    }
    f[0]=0;
    top=0;
    sta[++top]=0;
    for(int i=1;i<=n;i++)
    {
        while(top>1&&slope(sta[top-1],sta[top])<=2*i)top--;
        if(sta[top])f[i]=f[sta[top]-1]+1ll*(i-sta[top])*(i-sta[top]+1)/2-(sum[i]-sum[sta[top]]);
                else f[i]=1ll*i*(i+1)/2-sum[i];
                f[i]=max(f[i],f[i-1]);
        while(top>1&&slope(sta[top-1],sta[top])<slope(sta[top],i))top--;
                sta[++top]=i;
    }
}
inline ll C(int x)
{
    return 2ll*dp2[x+2]-2ll*sum[x]+3ll*x+1ll*x*x;
}
inline double slopeC(int x,int y)
{
    return 1.0*(C(y)-C(x))/(y-x);
    
}
inline ll G(int x)
{
    if(x<=1)return -3ll*x+1ll*x*x+2ll*sum[x-1];
    return 2ll*dp1[x-2]-3ll*x+1ll*x*x+2ll*sum[x-1];
}
inline double slopeG(int x,int y)
{
    return 1.0*(G(y)-G(x))/(y-x);
    
}
inline void find(int l,int r)
{
    if(l==r)
    {
        if(l>1)h[l]=max(h[l],dp1[l-2]+dp2[l+2]+1-val[l]);
        else h[l]=max(h[l],dp2[l+2]+1-val[l]);
        return;
    }
    int mid=(l+r)>>1;
    find(l,mid);
    find(mid+1,r);
    top=0;
    ll ans=-1000000000000ll;
    for(int i=mid+1;i<=r;++i){
        while(top>1&&slopeC(sta[top-1],sta[top])<slopeC(sta[top],i))top--;
        sta[++top]=i;
    }
    for(int i=l;i<=mid;++i){
        while(top>1&&slopeC(sta[top-1],sta[top])<=2*i)top--;
        if(i>1)ans=max(ans,dp1[i-2]+dp2[sta[top]+2]+1ll*(sta[top]-i+1)*(sta[top]-i+2)/2-(sum[sta[top]]-sum[i-1]));
        else ans=max(ans,dp2[sta[top]+2]+1ll*(sta[top]-i+1)*(sta[top]-i+2)/2-(sum[sta[top]]-sum[i-1]));
        h[i]=max(h[i],ans);
    }
    top=0;
    for(int i=l;i<=mid;++i){
        while(top>1&&slopeG(sta[top-1],sta[top])<slopeG(sta[top],i))top--;
        sta[++top]=i;
    }
    ans=-1000000000000ll;
    for(int i=mid+1;i<=r;++i){
       while(top>1&&slopeG(sta[top-1],sta[top])<=2*i)top--;
       if(sta[top]>1)num[i]=dp1[sta[top]-2]+dp2[i+2]+1ll*(i-sta[top]+1)*(i-sta[top]+2)/2-(sum[i]-sum[sta[top]-1]);
       else num[i]=dp2[i+2]+1ll*(i-sta[top]+1)*(i-sta[top]+2)/2-(sum[i]-sum[sta[top]-1]);
    }
    for(int i=r;i>mid;--i){
        ans=max(ans,num[i]);
        h[i]=max(h[i],ans);
    }
}
ll read(){
    ll x=0,f=1;
    char ch;
    while((ch=getchar())<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        val[i]=read();
        h[i]=-66666666666666ll;
    }
    dp();
        for(int i=0;i<=n;++i)dp1[i]=f[i];
        reverse(val+1,val+n+1);
        dp();
        for(int i=1;i<=n;++i)dp2[n-i+1]=f[i];
        reverse(val+1,val+n+1);
        for(int i=1;i<=n;++i)sum[i]=sum[i-1]+val[i];
        find(1,n);
    m=read();
        for(int i=1;i<=m;++i){
            p=read();x=read();
            printf("%lld\n",max(dp1[p-1]+dp2[p+1],h[p]+val[p]-x));
        }
    return 0;
}


Measured memory_bytes: 35328