#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
#define Maxn 300010
int val[Maxn];
ll sum[Maxn];
ll f[Maxn];
ll dp1[Maxn],dp2[Maxn];
int sta[Maxn],top;
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(register int i=1;i<=n;++i)sum[i]=sum[i-1]+val[i];
    f[0]=0;
    top=0;
    sta[++top]=0;
    for(register 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;
    }
}

ll h[Maxn];
ll num[Maxn];
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 calc(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;
    calc(l,mid);
    calc(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);
    }
}

inline void rd(int &x){
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
}

int main(){
    rd(n);
    for(register int i=1;i<=n;++i)rd(val[i]),h[i]=-1000000000000ll;
    dp();
    for(register int i=0;i<=n;++i)dp1[i]=f[i];
    reverse(val+1,val+n+1);
    dp();
    for(register int i=1;i<=n;++i)dp2[n-i+1]=f[i];
    reverse(val+1,val+n+1);
    for(register int i=1;i<=n;++i)sum[i]=sum[i-1]+val[i];
    calc(1,n);
    rd(m);
    int p,x;
    for(int i=1;i<=m;++i){
        rd(p);rd(x);
        printf("%lld\n",max(dp1[p-1]+dp2[p+1],h[p]+val[p]-x));
    }
    return 0;
}
/*
--------------------- 
作者：ezoilearner 
来源：CSDN 
原文：https://blog.csdn.net/ezoilearner/article/details/83447864 
版权声明：本文为博主原创文章，转载请附上博文链接！
*/

Measured memory_bytes: 18944