// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$$$$$$$*ooo!ooooooooooooo!ooooo!oo!!!!!!!!!!!!o!o$&&&&&8&&&888&888&&8&8
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$$*ooooo*********oo****o!;;!!!!!!!!!o!!!!!$&&&&&&&888&&&&&&&&&8&&
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&$$$$$$&&&&&$****oo!!o!;!oo!o$88&&&&&&&&&8&&&&&&&&&&8
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&&&&&88&&&&$$$*oo!ooo!;*&88&&&&&&&&&&&&&&&&&&&&&
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&&&&&&&&88&&&&888&8&&888&&&&&&&&&&&&&$$$$**o!o$&&&&&&&&&&&&&&&&&&&&&&&&
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&8&8&8888&8&&888&&&&&888888888888888888&&&88&&&&&&88&&&&8&&&&&&&&&&&&&&&&8
// $$$$$$$$$$$$&&&$$$$$$$$$$&&&888&8&&&&&&&8888888&&&&&88&&8&&&8&888888&&88&&&8&&&&&&&8&&&&&&&&&&&&&&&&&8&&&
// $$$$*$***oooooooooooooo$&888888&&8&8888888&&&&&8888&&8888&88&&&&8&&&&8&&&&&&8&&&&&&&&&&&&&&&&&8&8&&&&8&&&
// !!!!!!!!!!!!;!ooo!o*$$&&&&&88&8888888888888888888888&&8&&&88&&88&8&88888&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&88&
// !!!!!!!!!ooooo!!!!o$&&&&8&888888888888888888888888888888&&&&&&8888&&888&88&&&88&&&&&&&&&&&&&&&&&&&&&&&&&&
// !!!!!!!!!!!!!!!oo$$&8&888888888888888888888888888&&88&88&8&&88&&88&&88&888&&88888&&&8888&&&&&88&&&&&8888&
// !ooooooooooooo!o$&&&88888888888888&&88888888888&&&&8&&&&&&&&&&&&&888&&&&888&88&&&8&&88888&&&&&&&&&&&&&&&&
// ooooooo**o**o*$$$88&&&888888888888&8&&&8&&&888888&8&&&&8&&&&88&&888&&8888&8&888&8&&88888&8&&&&&&&&&&&&&&$
// *$$$$*$$**$$$$$&&&&88888&8&8&888&&88&888&&&88&&8&&&&&8&8&&&&&&&&&&&&8888888888888888&88888&8888&&&&&&&$$$
// $$&&$$&$$$$$$$&88&&&88&&8888888888&&&&&&&&&&8&&&&&&&&&&&&&&&&&&$&&&$$&&&&&88888888888888&&88&8&&&&&$$$$**
// &&&&&&&&&&$$$$&88&&&&88888&&&88888&&&&&&&&$$$&&&&&&&&&&&&&&&&&&&$$$$$$&&&&&&&8&88888888&8&&&8888&&&$$$*o*
// &&&&&&&8&&&&&&&&&8888&88888&8&&&&&&&&&&$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&&&8&88888888&&88&&&&8&&$$***
// &&&&&&8&&&&&&&&&&&&8&&&&&&888&8&&&&&&$$$$$$*********$***********$$$$$$$$$&&&&&&&&&&&88888&&88888&8&&&$*o*
// &&&&&&&&&&&&&&88&&&&&&&&&&&&&&&&&&&$$$$$$$*o****oooooooooooooooo****$$$$$$$$$$&&&&&&&&888&88&&&&&8&&&$oo*
// &&&&&&&&&&&&&&&&&&&&8888&&&8&&&&&&$$*$$**oooooo!!!oooooooooooooo**********$$$$$$$$$$&&&&&88&888&&&&&&$oo*
// &&&&&&&&&&&&&&&&&&&&&&&8&&&&&&&&&$$*****oooooooooooo!ooooo!ooooooo*o********$$$$$$$$$$$$&&&8&&88&&&8&$oo*
// &&&&&&&&&&&&&&&&&&&&&&&8&&&&&&&&$$$*****oooooooooooooooooooooooooooooo************$$$$$$$$$$&&88&&&8&$oo*
// &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&$$$$******oooooooooooo!ooooooooo*o**o***********$*****$$$$$$$$&8&&&&&8$o!*
// &&&&&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$*****oooooooooooooooooooooooooooooo***************$**$$*$$$88&&&&8&o!o
// &&&&&&&&&&&&&&&&&&&&&&&&&&&&$$&$$$$$********oooooooooooooooooooo*o******************$$**$$$*$$&8&&&&&$*o*
// &&&&&&&&&&&&&&&&&&&&&&&&&&&$$$&&$$$$**********oooooo!oooooooooo*ooo*********************$$$$$$$8&&&8&$***
// &&&&&&8&&&&&&&&8&&&&&&&&&&$$&$$$$$***********ooooooooooooooooooooooooo******************$$$$$$$&&&$8&$***
// &&&&&&&&&&&&&&&&&&&&&&&&&&$&$$$$**************ooooooooooooo*o****o************************$$$$$&&&&&$$ooo
// $$$$$$$$$$$$$$&&&&&&&&&&&$&&&$$$***************o***oo****ooo*******************************$$$$$$&&$$*oo*
// $$$$$$$$$$$****$&&&&&&&&&&&$$$$*************$$$$$$$$*$$************************************$$$$$&8&$$**o*
// $$*$**$$$**$$$**$$&&&&&&&&$$*************$$$$$$$&&&&88&&$$$$**$*************************$***$*$$&88*ooo**
// $$$$$$$$$$$$$$$$$$$&&$&&&&&$*************$$$$$$$$$$$&&$&&&&&&&$$$$$$$$$$$*$$$$$$$$$$*$$$$$$$&$$$&88*o****
// $$$$$$$$$*$$$**$$$$$$&&&&&$$*o************$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&&&&&&&&&$$&$******
// $$$$$$$$$$**oo!o*$$$$$&$$&&*oo********$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&888888&&&&&$$&$$&&$******
// $$$$$*$$*******$$$$$$$&&$8&$***********$$$$$$$$$$&&&&&&$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$$******
// $$$$$*$**oo*$$$$**$$*$$$$$$$************$$$$$&&&&&8&&&$$$&$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$***$$*
// &$$$$$***o**$$$$$$$***$$$$$******oo*oooooooo***$$$$$$$$$$$$$$$$$$$$$**$$$$$$$$$$&&&&&&&&$$$$$$$$$$*****$$
// &&$$*****ooo*****ooo**$$$$$******ooooooooooooo***$$$$$$$$$$$$$******ooo*$$$$$$&8888&&$$$&8&$$$$$$$*$*$$$$
// &&&$$****o**oooo******$$$$$********oooooooooooooo**o***$***$$$***$*o!!oo*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
// $$$&$$$**o**o*ooooo***$$$$$$*******oooooooo!!ooooooooooo******oo*ooooooo**$$$$$$$$$$$$$$$$$$*$$$$$$$$$$$$
// $$$$$$$$$*ooo***o*****$$$$*$*******oooooooooooooooooooo*o**ooooooooo!oooo**$$$$$$*$$$$$$$$$$$$$*$$$$$$$$$
// $$$$$$$$$$**ooo**o****$$$$***********ooooooooooooooooooo*oo!!!!!ooo!o!!!o*****$$$*$$**$$*****$$$$$$$$$$$$
// $$$$$$$$$$$****ooooo***$$$*************oo*ooooooooooo*****$$$$$**oooo!!!o***$$**$**$****$****$$$$$$$$$$$$
// &$$$$$$$$$$***$$$$$$&$$$$$*************************$$$$$$$*ooooooo!o!!ooooo**$$*******$****$$$$$$$$$$$$$$
// $$$$$$$$$$$$**$$$$$$$$$$$***********************$$$$$$$$$*oo!!ooooooooooooo**$$$$$$$********$**$$$$$$$$$$
// $$$$$$$$$$$$$$$$$$$$$$$$$**************$$$$$$$$$$$$$$$$$$$*$*ooooo*************$$$$$$$$$$$$*$$*$$$&$$$$$$
// $$$$$$$$$$$$$$$$$$$$$$$$$$************$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&&&$&
// $$$$$$$$$$$$$$$$$$$$$$$$$$*************$$$$$$$$$$$$$$$$$**$$$$$$$$$$$$$$&$$&&$$$$$$$$$$$$$$$$$$$$$$&$$&$&
// $$$$$$$$$$$$$$$$$$$$$$$$$$**********$*$$$$$$$$$$$$$$$$$****$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$&
// $$$$$$$$$$$$$$$$$$$$$$$$$$$***********$$$$$$$$$$$$$$$$**ooooo*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$*$$******$$$$$$$$$$$$$$*$$$**$*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$******$$**$*$$$$$$&&8888&&&$$$$$$$$&&&&&&&&$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
// $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*$*$$***$$$$$$$$$&&$$$$**$$*$$$$$$$$$$$$$$&&8&&&$$$$$$$$$$$$$$$$$$$$$&$
// $&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$****$$$$$$$$$$$***ooooooo**ooo**o!oo$$&&$$$$$$$$$$$$$$$$$$***$$&$
// &&&&&&8&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$*$$$$$***$$$$$&$$$$****!oo*$$$$$&&$$$$$$$$$$$$$$$$$&&$$$$*$$
// 8&&&&&&&&88&88&8&&&8&&&&&&&&&&&&$$$$$$$$$$***$$***$$****o!!o!!*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$$$$
// 8&&&&&&&&&&&&&&&&&&&&&&&&8&&&&&&&&&&&&$$$$$$$$$********$*$$*********$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$&$$
// &888888888&8&&&&8&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$****$*****$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$***$$$$$$$$$&$$
// 888&&&&888&&8888&88&&88&&8&&88&8&88&8888&&&&$$$$$*oo****$$$$$$$$$$$$$$&$$$$$$$$$$$$$$$$$$$$$$$*$$$$&&888&
// &&88888888888888&88&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&$$*oo****$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*$$$$$**$$$$$&888
// 8888888&88&&88&&&8&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&$$$*o*****$$$$$$$$$$$$$$$$$$$$$$$$$$$$*$$$$$$$$$$$$88&
// 888888888888&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&&&&88&$$oo***$$$**$$$$$$$$$$$$$$$$$********$$$$$$$$*$888
// &88888888&&8&&&&&&&&&8&8&&&&&&&&&&&&&&&&8&88&&8&8&&&&&88&&$$$***$*$$$$$$$$$$$$$$$$$*$$$$$$$*$$$$$$$*$**$&
// 8888&888&888&&&&&&&88&&&&&&&&&&&8&&&888&&&&&&&&&&&&8888&&&&&$$**$$$$$$$$$$$$$$$$$$**$$****$$$$$$$$$$$$$o$
// &88&888888&&88&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&88888&8&8&&$$$$$$$$$$$$$$$$$$$*$$$$*$*$$$*$$$$$$$$$$$$
// 8888&&&&&&&&&&&&8&&&8&&&&&&&&&&&&&&&8&&8&&&&&&&&88&&&&&&888&8&&&$$$$$$$$$$$$$$*****$$*$$$$$$$$$$$$$$$$$$$
// &88&&8&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&&&&&88&&&&8&8888&&&8&888&&&8&8888&$*$$$$$***$$$$*$$$$$$$$$$$$$$$$
#include <cstdio>
#include <utility>
#define MP make_pair
#define FR first
#define SE second
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
namespace IO{
    const int S=10000000;
    char buf[S];
    int pos;
    void load(){
        fread(buf,1,S,stdin);
        pos=0;
    }
    char getChar(){
        return buf[pos++];
    }
    int getInt(){
        int x=0,f=1;
        char c=getChar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getChar();}
        while('0'<=c&&c<='9'){x=x*10+c-'0';c=getChar();}
        return x*f;
    }
}
using IO::getInt;
const LL LINF=1ll<<60;
const int N=300010;
int n;
int a[N];
LL sum[N];
inline LL max(LL x,LL y){
	return x>y?x:y;
}
inline void swap(int &x,int &y){
	x^=y^=x^=y;
}
void reverse(){
	for(int i=1;i<=(n>>1);i++)
		swap(a[i],a[n-i+1]);
}
void calcPrefix(){
	sum[0]=0;
	for(int i=1;i<=n;i++) 
		sum[i]=sum[i-1]+a[i];
}
void readData(){
	n=getInt();
	for(int i=1;i<=n;i++) a[i]=getInt();
	calcPrefix();
}
LL f[N];
namespace HULL{
	PLL sta[N];
	int top;
	void reset(){
		top=0;
	}
	PLL generate(LL x){
		return MP(x,f[x]+sum[x]+(x*(x-1)>>1));
	}
	inline bool legal(PLL &a,PLL &b,PLL &c){
		return (b.SE-a.SE)*(c.FR-b.FR)>(c.SE-b.SE)*(b.FR-a.FR);
	}
	inline bool slopeLess(PLL &a,PLL &b,LL k){
		return (b.SE-a.SE)<=k*(b.FR-a.FR);
	}
	void push(int x){
		PLL cur=generate(x);
		while(top>1&&!legal(sta[top-1],sta[top],cur))
			top--;
		sta[++top]=cur;
	}
	int query(int i){
		while(top>1&&slopeLess(sta[top-1],sta[top],i))
			top--;
		return sta[top].FR;
	}
}
void dp(){
	HULL::reset();
	f[0]=0;
	HULL::push(0);
	for(int i=1;i<=n;i++){
		int j=HULL::query(i);
		f[i]=max(f[j]-(sum[i]-sum[j])+(1ll*(i-j)*(i-j+1)>>1),f[i-1]);
		HULL::push(i);
	}
}
LL fl[N],fr[N],must[N];
void dpLeftRight(){
	dp();
	for(int i=1;i<=n;i++) fl[i]=f[i];
	reverse();
	calcPrefix();
	dp();
	for(int i=1;i<=n;i++) fr[i]=f[n-i+1];
	reverse();
	calcPrefix();
}
void swapLR(){
	for(int i=1;i<=n;i++) 
		swap(fl[i],fr[n-i+1]);
}
LL g[N];
void divide(int l,int r,int offset){
	if(l==r){
		g[l]=max(g[l],fl[l-1]+fr[r+1]+1-a[l]);
		return;
	}
	int mid=(l+r+offset)>>1;
	HULL::reset();	
	for(int i=l-1;i<mid;i++){
		f[i]=fl[i];
		HULL::push(i);
	}
	static LL t[N];
	for(int i=mid+1;i<=r;i++){
		int j=HULL::query(i);
		t[i]=f[j]-(sum[i]-sum[j])+1ll*(i-j)*(i-j+1)/2+fr[i+1];
	}
	for(int i=r-1;i>mid;i--) t[i]=max(t[i],t[i+1]);
	for(int i=mid+1;i<=r;i++) g[i]=max(g[i],t[i]);
	divide(l,mid,offset);
	divide(mid+1,r,offset);
}
void calcMust(){
	for(int i=1;i<=n;i++) must[i]=-LINF;
	for(int i=1;i<=n;i++) g[i]=-LINF;
	divide(1,n,0);
	for(int i=1;i<=n;i++) must[i]=max(must[i],g[i]);
	reverse();
	swapLR();
	calcPrefix();
	for(int i=1;i<=n;i++) g[i]=-LINF;
	divide(1,n,-1);
	for(int i=1;i<=n;i++) must[i]=max(must[i],g[n-i+1]);
	reverse();
	swapLR();
}
void answerQuery(){
	int m,x,y;
	m=getInt();
	for(int i=1;i<=m;i++){
		x=getInt(); y=getInt();
		printf("%lld\n",max(fl[x-1]+fr[x+1],must[x]-(y-a[x])));
	}
}
int main(){
	IO::load();
	readData();
	dpLeftRight();
	calcMust();
	answerQuery();
	return 0;
}


Measured memory_bytes: 31872