#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int MAXN=6e5+10,MAXM=4e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=998244353,mod=998244353;
const int Lim=(1<<19);

ll f[MAXN],g[MAXN],h[MAXN],a[MAXN],s[MAXN],tmp[MAXN];
int n,m,stk[MAXN],top;

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

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

ll calc(ll x,ll y)
{
    return (x-y)*(x-y+1)/2ll;
}

double Kf(int x,int y)
{
    return (1.0*Yf(x)-1.0*Yf(y))/(1.0*x-1.0*y);
}

double Kg(int x,int y)
{
    return (1.0*Yg(x)-1.0*Yg(y))/(1.0*x-1.0*y);
}

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

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

double KF(int x,int y)
{
    return (1.0*YF(x)-1.0*YF(y))/(1.0*x-1.0*y);
}

double KG(int x,int y)
{
    return (1.0*YG(x)-1.0*YG(y))/(1.0*x-1.0*y);
}

void solve(int l,int r)
{
    if(l==r)return h[l]=max(h[l],f[l-1]+g[l+1]+1-a[l]),void();
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    s[l-1]=s[r+1]=top=0;
    for(int i=l;i<=r;i++)s[i]=s[i-1]+a[i];
    for(int i=l-1;i<=mid;i++)
    {
        while(top>1&&Kf(stk[top],stk[top-1])<=Kf(i,stk[top]))top--;
        stk[++top]=i;
    }
    for(int i=mid+1;i<=r;i++)
    {
        while(top>1&&KF(stk[top],stk[top-1])<=i)top--;
        tmp[i]=f[stk[top]]+calc(i,stk[top])-s[i]+s[stk[top]]+g[i+1];
    }
    ll ans=-llINF;
    for(int i=r;i>mid;i--)
    {
       ans=max(ans,tmp[i]);
       h[i]=max(h[i],ans);
    }
    top=0;
    for(int i=r;i>=l;i--)s[i]=s[i+1]+a[i];
    for(int i=r+1;i>mid;i--)
    {
        while(top>1&&Kg(stk[top],stk[top-1])>=Kg(i,stk[top]))top--;
        stk[++top]=i;
    }
    for(int i=mid;i>=l;i--)
    {
        while(top>1&&KG(stk[top],stk[top-1])>=i)top--;
        tmp[i]=g[stk[top]]+calc(stk[top],i)-s[i]+s[stk[top]]+f[i-1];
    }
    ans=-llINF;
    for(int i=l;i<=mid;i++)
    {
        ans=max(ans,tmp[i]);
        h[i]=max(h[i],ans);
    }
}

int main()
{
    scanf("%d",&n);
    top=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        h[i]=-llINF;
        s[i]=s[i-1]+a[i];
    }
    stk[++top]=0;
    s[n+1]=s[n];
    for(int i=1;i<=n+1;i++)
    {
        while(top>1&&Kf(stk[top],stk[top-1])<=i)top--;
        f[i]=max(f[i-1],f[stk[top]]+calc(i-1,stk[top])-s[i-1]+s[stk[top]]);
        while(top>1&&Kf(stk[top],stk[top-1])<=Kf(stk[top],i))top--;
        stk[++top]=i;
    }
    top=0;
    stk[++top]=0;
    reverse(a+1,a+n+1);
    for(int i=1;i<=n+1;i++)s[i]=s[i-1]+a[i];
    for(int i=1;i<=n+1;i++)
    {
        while(top>1&&Kg(stk[top],stk[top-1])<=i)top--;
        g[i]=max(g[i-1],g[stk[top]]+calc(i-1,stk[top])-s[i-1]+s[stk[top]]);
        while(top>1&&Kg(stk[top],stk[top-1])<=Kg(stk[top],i))top--;
        stk[++top]=i;
    }
    reverse(g,g+n+2);
    reverse(a+1,a+n+1);
    solve(1,n);
    int m;
    //for(int i=1;i<=n;i++)cout<<i<<" "<<f[i]<<" "<<g[i]<<" "<<h[i]<<endl;
    scanf("%d",&m);
    while(m--)
    {
        int p,x;
        scanf("%d%d",&p,&x);
        printf("%lld\n",max(f[p]+g[p],h[p]+a[p]-x));
    }
    return 0;
}


Measured memory_bytes: 27136