#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > 
#define pii pair<int,int> 
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define SZ(x) ((int)x.size())
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<16;
char buffer[BufferSize],*Bufferhead,*Buffertail;
bool Terminal;
inline char Getchar(){
	if(Bufferhead==Buffertail){
		int l=fread(buffer,1,BufferSize,stdin);
		if(!l){Terminal=1;return 0;}
		Buffertail=(Bufferhead=buffer)+l;
	}
	return *Bufferhead++;
}
template<class T>inline bool read(T &x){
	x=0;char c=Getchar(),rev=0;
	while(c<'0'||c>'9'){rev|=c=='-';c=Getchar();if(Terminal)return 0;}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
	if(c=='.'){
		c=Getchar();double t=0.1;
		while(c>='0'&&c<='9') x=x+(c-'0')*t,c=Getchar(),t=t/10;
	}
	x=rev?-x:x;
	return 1;
}
template<class T1,class T2> inline bool read(T1 &x,T2 &y){return read(x)&read(y);}
template<class T1,class T2,class T3> inline bool read(T1 &x,T2 &y,T3 &z){return read(x)&read(y)&read(z);}
template<class T1,class T2,class T3,class T4> inline bool read(T1 &x,T2 &y,T3 &z,T4 &w){return read(x)&read(y)&read(z)&read(w);}
inline bool reads(char *x){
	char c=Getchar();
	while(c<33||c>126){c=Getchar();if(Terminal)return 0;}
	while(c>=33&&c<=126) (*x++)=c,c=Getchar();
	*x=0;return 1;
}
template<class T>inline void print(T x,const char c='\n'){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[20];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
//--------------------------------head---------------------------------------------

const int inf=0x3f3f3f3f;
const int N=300005,M=100005,mod=1e9+7;
template<class T,class S> inline void ch(T &x,const S y){x=(x+y)%mod;}
inline int exp(int x,int y,const int mod=::mod){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int n,m,T[N],q[N];
ll s[N],f[N],g[N];

inline ll get(ll *f,int j){
	return f[j]+(ll)j*(j-1)/2+s[j];
}
void makedp(ll *dp){
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+T[i];
	int tot=1;
	dp[0]=0;q[1]=0;
	for(int i=1;i<=n;i++){
		while(tot>1&&get(dp,q[tot])-get(dp,q[tot-1])<=(ll)i*(q[tot]-q[tot-1])) tot--;
		dp[i]=max(dp[i-1],get(dp,q[tot])-(ll)i*q[tot]+(ll)i*(i+1)/2-s[i]);
//		if(dp[i]==dp[i-1]) continue;
		while(tot>1&&(ll)(q[tot]-q[tot-1])*(get(dp,i)-get(dp,q[tot]))>=(ll)(i-q[tot])*(get(dp,q[tot])-get(dp,q[tot-1]))) tot--;
		q[++tot]=i;
	}
//	dprintf("%lld\n",dp[n]);
}

ll ans[N],dp[N];
int p[N],v[N],rk[N],tmp[N];

inline void solve(int l,int r,int x,int y){
	if(x>y) return;
	if(r<=l+1) return;
	
	for(int i=l;i<=r;i++) dp[i]=-(1ll<<60);
	int mid=l+r>>1,tot;
	tot=0;
	for(int i=l;i<=mid;i++){
		while(tot>1&&(ll)(q[tot]-q[tot-1])*(f[i]-f[q[tot]])>=(ll)(i-q[tot])*(f[q[tot]]-f[q[tot-1]])) tot--;
		q[++tot]=i;
	}
	for(int i=mid+1;i<=r;i++){
		while(tot>1&&f[q[tot]]-f[q[tot-1]]<=(ll)i*(q[tot]-q[tot-1])) tot--;
		dp[i]=g[i]+f[q[tot]]-(ll)i*q[tot];
	}
	for(int i=r-1;i>mid;i--) gmax(dp[i],dp[i+1]);
	for(int i=x;i<=y;i++){
		int k=rk[i];
		if(p[k]<=mid||p[k]==r) continue;
		gmax(ans[k],dp[p[k]+1]+T[p[k]]-v[k]);
	}
	
	tot=0;
	for(int i=mid+1;i<=r;i++){
		while(tot>1&&(ll)(q[tot]-q[tot-1])*(g[i]-g[q[tot]])>=(ll)(i-q[tot])*(g[q[tot]]-g[q[tot-1]])) tot--;
		q[++tot]=i;
	}
	for(int i=l;i<=mid;i++){
		while(tot>1&&g[q[tot]]-g[q[tot-1]]<=(ll)i*(q[tot]-q[tot-1])) tot--;
		dp[i]=f[i]+g[q[tot]]-(ll)i*q[tot];
	}
	for(int i=l+1;i<=mid;i++) gmax(dp[i],dp[i-1]);
	for(int i=x;i<=y;i++){
		int k=rk[i];
		if(p[k]>mid||p[k]==l) continue;
		gmax(ans[k],dp[p[k]-1]+T[p[k]]-v[k]);
	}
	
	int xx=x,yy=y;
	for(int i=x;i<=y;i++)
		if(p[rk[i]]<=mid) tmp[xx++]=rk[i]; else tmp[yy--]=rk[i];
//	dprintf("%d %d\n",xx,yy);
	for(int i=x;i<=y;i++) rk[i]=tmp[i];
	solve(l,mid,x,yy);solve(mid+1,r,xx,y);
}

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
//	file("f");
#endif
	read(n);
	for(int i=1;i<=n;i++) read(T[i]);
	makedp(f);
	reverse(T+1,T+n+1);
	makedp(g);
	reverse(g+1,g+n+1);reverse(T+1,T+n+1);
	read(m);
	for(int i=1;i<=m;i++)
		read(p[i],v[i]),rk[i]=i,ans[i]=f[p[i]-1]+g[p[i]+1];
	for(int i=1;i<=n;i++) s[i]=s[i-1]+T[i];
	for(int i=0;i<=n;i++) f[i]+=(ll)i*(i+1)/2+s[i];
	for(int i=1;i<=n+1;i++) g[i]+=(ll)i*(i-1)/2-s[i-1];
	solve(0,n+1,1,m);
	for(int i=1;i<=m;i++)
		print(ans[i]);
	return 0;
}

Measured memory_bytes: 21376