// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define N 333333

#define rev(a) reverse(a+1,a+n+1)

#define ll long long

 

int n,t,a[N];

long long s[N],l[N],r[N],f[N],g[N],h[N],q[N];

int read(){

	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());

	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;

}

ll sum(int n){return (ll)n*(n+1)/2;} 

double slope(int x,int y){return (double)(g[x]-g[y])/(x-y);}

void pop(int x){for (;t>1&&slope(q[t-1],q[t])<=x;t--);}

void push(int x){

	for (;t>1&&slope(q[t-1],q[t])<=slope(q[t],x);t--);q[++t]=x;

}

void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}

void calc(ll *f){

	int i;q[t=1]=0;init_s();

	for (i=1;i<=n;i++){

		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);

		g[i]=f[i]+sum(i-1)+s[i];push(i);

	}

}

 

void solve(int x,int y){

	if (x==0&&y==n) for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

	if (x==y) return;

	int mid=(x+y)/2;t=0;

	for (int i=x;i<=mid;i++){

		g[i]=l[i]+1ll*i*(i-1)/2+s[i];

		push(i);

	}

	for (int i=mid+1;i<=y;i++){

		pop(i);

		h[i]=g[q[t]]-1ll*i*q[t]+1ll*i*(i+1)/2-s[i]+r[i+1];

	}

	for (int i=y-1;i>mid;i--) h[i]=max(h[i],h[i+1]);

	for (int i=mid+1;i<=y;i++) f[i]=max(f[i],h[i]);

	solve(x,mid);solve(mid+1,y);

}

 

int main(){

	n=read();

	for (int i=1;i<=n;i++) a[i]=read(),f[i]=-1e18;

	calc(l);rev(a);calc(r);rev(a);rev(r);

	solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	for (int m=read();m;m--){

		int p=read(),x=read();

		printf("%lld\n",max(l[p-1]+r[p+1],a[p]+f[p]-x));

	}

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

#define ll long long

#define rev(a) reverse(a+1,a+n+1)

using namespace std;

const int N=3e5+5,inf=1e9;

int n,i,a[N];

ll s[N],g[N],l[N],r[N],f[N];

int read(){

	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());

	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;

}

void write(ll x){if (x>9) write(x/10);putchar(x%10+48);}

ll sum(int n){return (ll)n*(n+1)/2;}

int t,q[N];

double cal(int x,int y){return (double)(g[x]-g[y])/(x-y);}

void pop(int x){for (;t>1&&cal(q[t-1],q[t])<=x;t--);}

void push(int x){

	for (;t>1&&cal(q[t-1],q[t])<=cal(q[t],x);t--);q[++t]=x;

}

void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}

void init(ll *f){

	int i;q[t=1]=0;init_s();

	for (i=1;i<=n;i++){

		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);

		g[i]=f[i]+sum(i-1)+s[i];push(i);

	}

}

ll w[N];

void work(int x,int y){

	if (x==y) return;int i,m=x+y>>1;t=0;

	for (i=x;i<=m;i++) g[i]=l[i]+sum(i-1)+s[i],push(i);

	for (;i<=y;i++) pop(i),

		w[i]=l[q[t]]+r[i+1]+sum(i-q[t])-s[i]+s[q[t]];

	for (f[y]=max(f[y],w[y]),i=y-1;i>m;i--)

		f[i]=max(f[i],w[i]=max(w[i],w[i+1]));

	work(x,m);work(m+1,y);

}

int main(){

	for (n=read(),i=1;i<=n;i++) a[i]=read(),f[i]=-inf;

	init(l);rev(a);init(r);rev(a);rev(r);

	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	for (i=read();i--;putchar('\n')){

		int x=read(),k=read();

		write(max(l[x-1]+r[x+1],f[x]+a[x]-k));

	}	

}

// Fastest known solution for this problem: