#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 300010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,q;

int t[maxn];

int Q[maxn],top;

ll sm[maxn],f[maxn],y[maxn],pre[maxn],suf[maxn],tmp[maxn],Ans[maxn];

void DP(){
	REP(i,1,n)sm[i]=sm[i-1]+t[i];
	Q[top=1]=0;
	REP(i,1,n){
		f[i]=f[i-1];
		while(top>1&&(y[Q[top]]-y[Q[top-1]])<=2ll*i*(Q[top]-Q[top-1]))top--;
		f[i]=max(f[i],f[Q[top]]+1ll*(i-Q[top])*(i-Q[top]+1)/2+sm[Q[top]]-sm[i]);
		y[i]=f[i]*2+1ll*i*i-i+sm[i]*2;
		while(top>1&&(y[Q[top]]-y[Q[top-1]])*(i-Q[top])<=(y[i]-y[Q[top]])*(Q[top]-Q[top-1]))top--;
		Q[++top]=i;
	}
}

void solve(int l,int r){
//	cout<<l<<' '<<r<<endl;
	if(l==r){
		Ans[l]=max(Ans[l],pre[l-1]+suf[l+1]+1-t[l]);
		return;
	}
	int M=l+r>>1;
	top=0;
	REP(i,l-1,M-1){
		y[i]=pre[i]*2+1ll*i*i-i+sm[i]*2;
		while(top>1&&(y[Q[top]]-y[Q[top-1]])*(i-Q[top])<=(y[i]-y[Q[top]])*(Q[top]-Q[top-1]))top--;
		Q[++top]=i;
	}
	REP(i,M,r){
		while(top>1&&(y[Q[top]]-y[Q[top-1]])<=2ll*i*(Q[top]-Q[top-1]))top--;
		tmp[i]=pre[Q[top]]+suf[i+1]+1ll*(i-Q[top])*(i-Q[top]+1)/2+sm[Q[top]]-sm[i];
	}
	RREP(i,r-1,M)tmp[i]=max(tmp[i],tmp[i+1]);
//	REP(i,M+1,r)cout<<tmp[i]<<' ';cout<<endl;
	REP(i,M,r)Ans[i]=max(Ans[i],tmp[i]);
	solve(l,M);solve(M+1,r);
	
}

void Work(){
	read(q);
	while(q--){
		int p,x;read(p,x);
		ll ans=max(pre[p-1]+suf[p+1],Ans[p]-x+t[p]);
		printf("%lld\n",ans);
	}
}

void Init(){
	read(n);
	REP(i,1,n)read(t[i]);
	DP();REP(i,1,n)pre[i]=f[i];
	reverse(t+1,t+n+1);
	DP();REP(i,1,n)suf[i]=f[i];
	reverse(t+1,t+n+1);reverse(suf+1,suf+n+1);
	
//	REP(i,1,n)cout<<pre[i]<<' ';cout<<endl;
//	REP(i,1,n)cout<<suf[i]<<' ';cout<<endl;
	
	REP(i,1,n)Ans[i]=-t[i],sm[i]=sm[i-1]+t[i];	
	solve(1,n);
	reverse(t+1,t+n+1);REP(i,1,n)sm[i]=sm[i-1]+t[i];
	reverse(pre+1,pre+n+1);reverse(suf+1,suf+n+1);reverse(Ans+1,Ans+n+1);REP(i,1,n)swap(pre[i],suf[i]);
	solve(1,n);
	reverse(t+1,t+n+1);REP(i,1,n)sm[i]=sm[i-1]+t[i];
	reverse(pre+1,pre+n+1);reverse(suf+1,suf+n+1);reverse(Ans+1,Ans+n+1);REP(i,1,n)swap(pre[i],suf[i]);
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 21376