#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;
typedef double db;
int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

const int N=3*1e5+5;
const ll inf=1e16;

int n,m,x,y,a[N],stack[N],top;
ll f[N],g[N],h[N],ans[N],t[N],c[N],tmp[N],sum[N];

db P(int y,int x) {
    return (t[y]+(ll)y*(y-1)/2+sum[y]-t[x]-(ll)x*(x-1)/2-sum[x])*1.0/(y-x);
}

void Dp() {
    fo(i,1,n) sum[i]=sum[i-1]+a[i];stack[top=1]=0;
    fo(i,1,n) {
        while (top>1&&P(stack[top],stack[top-1])<=i) top--;
        int now=stack[top];
        t[i]=max(t[i-1],t[now]+(ll)(i-now)*(i-now+1)/2+sum[now]-sum[i]);
        while (top>1&&P(stack[top],stack[top-1])<P(i,stack[top])) top--;
        stack[++top]=i;
    }
}

void solve(int l,int r) {
    if (l==r) {
        h[l]=max(h[l],g[r+1]+f[l-1]+1-a[l]);
        return;
    }
    int mid=l+r>>1;
    stack[top=1]=l-1;
    fo(i,l,mid-1) {
        while (top>1&&P(stack[top],stack[top-1])<P(i,stack[top])) top--;
        stack[++top]=i;
    }
    fo(i,mid,r) {
        while (top>1&&P(stack[top],stack[top-1])<=i) top--;
        int now=stack[top];
        tmp[i]=t[now]+(ll)(i-now)*(i-now+1)/2+sum[now]-sum[i]+g[i+1];
    }
    fd(i,r-1,mid) tmp[i]=max(tmp[i],tmp[i+1]);
    fo(i,mid,r) h[i]=max(h[i],tmp[i]);
    solve(l,mid);solve(mid+1,r);
}
int main() {
    //freopen("genocide.in","r",stdin);
    //freopen("genocide.out","w",stdout);
    n=read();
    fo(i,1,n) a[i]=read();
    Dp();fo(i,1,n) f[i]=t[i];
    fo(i,1,n/2) swap(a[i],a[n-i+1]);
    Dp();fo(i,1,n) g[i]=t[n-i+1];
    fo(i,1,n) ans[i]=-inf;

    fo(i,1,n/2) swap(a[i],a[n-i+1]);
    fo(i,1,n) t[i]=f[i];
    fo(i,1,n) sum[i]=sum[i-1]+a[i];
    fo(i,1,n) h[i]=-inf;
    solve(1,n);
    fo(i,1,n) ans[i]=max(ans[i],h[i]);

    fo(i,1,n) swap(f[i],g[i]);
    fo(i,1,n/2) {
        swap(a[i],a[n-i+1]);
        swap(f[i],f[n-i+1]);
        swap(g[i],g[n-i+1]);
    }
    fo(i,1,n) t[i]=f[i];
    fo(i,1,n) sum[i]=sum[i-1]+a[i];
    fo(i,1,n) h[i]=-inf;
    solve(1,n);
    fo(i,1,n) ans[i]=max(ans[i],h[n-i+1]);

    fo(i,1,n/2) {
        swap(f[i],f[n-i+1]);
        swap(g[i],g[n-i+1]);
        swap(a[i],a[n-i+1]);
    }
    fo(i,1,n) swap(f[i],g[i]);

    for(m=read();m;m--) x=read(),y=read(),printf("%lld\n",max(f[x-1]+g[x+1],ans[x]+a[x]-y));
    return 0;
}