#include<cstdio>
#include<algorithm>
#define N_ 301000
using namespace std;
long long LD[N_], RD[N_], S[N_], DD[N_];
long long L[N_], R[N_];
int n, top;
struct point{
    long long a, b;
}st[N_];
long long Get(point p, int t){
    return p.a*t+p.b;
}
bool Over1(point a, point b, point c){
    if((b.b-a.b)*(a.a-c.a) <= (c.b-a.b)*(a.a-b.a))return true;
    return false;
}
bool Over2(point a, point b, point c){
    if((a.b-b.b)*(c.a-a.a) >= (a.b-c.b)*(b.a-a.a))return true;
    return false;
}
point MakeL(int i, long long d){
    return {-i, 1ll*i*(i-1)/2 + d + S[i]};
}
point MakeR(int i, long long d){
    return {-i, -S[i-1] + 1ll*i*(i+1)/2 + d};
}
void Do(int b, int e){
    if(b>e)return;
    int m = (b+e)>>1, i;
    top = 0;
    for(i=b-1;i<m;i++){
        point tp = MakeL(i,LD[i]);
        while(top>1 && Over1(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    for(i=m;i<=e;i++){
        while(top>1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        L[i] = Get(st[top],i) - S[i] + 1ll*i*(i+1)/2;
    }
    top = 0;
    for(i=e+1;i>m;i--){
        point tp = MakeR(i,RD[i]);
        while(top>1 && Over2(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    for(i=m;i>=b;i--){
        while(top > 1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        R[i] = Get(st[top],i) + S[i-1] + 1ll*i*(i-1)/2;
    }
    long long MM = -8e18;
    for(i=e;i>=m;i--){
        L[i] = L[i] + RD[i+1];
        MM = max(MM, L[i]);
        DD[i] = max(DD[i], MM);
    }
    MM = -8e18;
    for(i=b;i<=m;i++){
        R[i] = R[i] + LD[i-1];
        MM = max(MM, R[i]);
        DD[i] = max(DD[i], MM);
    }
    Do(b,m-1);
    Do(m+1,e);
}
int main(){
    int i, a, Q, b;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a);
        S[i] = S[i-1] + a;
        DD[i] = -8e18;
    }
    LD[0] = 0;
    st[++top] = {0,0};
    for(i=1;i<=n;i++){
        while(top>1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        LD[i] = max(Get(st[top],i) - S[i] + 1ll*i*(i+1)/2, LD[i-1]);
        point tp = MakeL(i,LD[i]);
        while(top>1 && Over1(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    RD[n+1] = 0;
    top = 0;
    st[++top] = MakeR(n+1,0);
    for(i=n;i>=1;i--){
        while(top > 1 && Get(st[top], i) <= Get(st[top-1], i))top--;
        RD[i] = max(Get(st[top],i) + S[i-1] + 1ll*i*(i-1)/2, RD[i+1]);
        point tp = MakeR(i,RD[i]);
        while(top>1 && Over2(st[top-1],st[top],tp))top--;
        st[++top] = tp;
    }
    Do(1, n);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&a,&b);
        printf("%lld\n",max(LD[a-1] + RD[a+1], DD[a] - b + S[a] - S[a-1]));
    }
}