///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
//                       _oo0oo_                         //
//                      o8888888o                        //
//                      88" . "88      ------ hzt1       //
//                      (| -_- |)                        //
//                      0\  =  /0                        //
//                    ___/`---'\___                      //
//                  .' \|     |// '.                     //
//                 / \|||  :  |||// \                    //
//                / _||||| -:- |||||- \                  //
//               |   | \  -  /// |     |                 //
//               | \_|  ''\---/''  |_/ |                 //
//               \  .-\__  '-'  ___/-. /                 //
//             ___'. .'  /--.--\  `. .'___               //
//          ."" '<  `.___\_<|>_/___.' >' "".             //
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |           //
//         \  \ `_.   \_ __\ /__ _/   .-` /  /           //
//     =====`-.____`.___ \_____/___.-`___.-'=====        //
//                       `=---='                         //
//                                                       //
//                                                       //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~       //
//                                                       //
//                 God-He Bless All.                     //
//           This Code Will Never Explode.               //
//                                                       //
//                                                       //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,Size,stdin);
        tail=(head=buffer)+l;
    }
    if(head==tail) return -1;
    return *head++;
}
typedef long long ll;
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
    return x*f;
}
typedef pair<int,int> pii;
const int maxn=300010;
const ll inf=1ll<<60;
int n,m;
ll S[maxn],A[maxn],f[maxn];
ll dpl[maxn],dpr[maxn];
struct Point {int x;ll y;}sta[maxn];
double slop(Point x,Point y) {
	return (double)(y.y-x.y)/(y.x-x.x);
}
ll getdp(int j,int i) {return f[j]-(S[i]-S[j])+(ll)(i-j)*(i-j+1)/2;}
void pre_dp() {
	rep(i,1,n) S[i]=S[i-1]+A[i];
	int top=0;
	sta[++top]=(Point){0,0};
	rep(i,1,n) {
		while(top>1&&getdp(sta[top].x,i)<getdp(sta[top-1].x,i)) top--;
		f[i]=max(f[i-1],getdp(sta[top].x,i));
		Point tmp=(Point){i,f[i]+S[i]+((ll)i*i-i)/2};
		while(top>1&&slop(sta[top-1],sta[top])<slop(sta[top],tmp)) top--;
		sta[++top]=tmp;
	}
}
ll g[maxn],cur[maxn];
ll getg(int i,int j) {return dpl[i-1]+dpr[j+1]+(ll)(j-i+1)*(j-i+2)/2-(S[j]-S[i-1]);}
void solve(int l,int r) {
	if(r-l+1<=10) {
		rep(i,l,r) {
			ll tmp=-inf;
			dwn(j,r,i) {
				tmp=max(tmp,getg(i,j));
				g[j]=max(g[j],tmp);
			}
		}
	}
	else {
		int mid=l+r>>1;
		solve(l,mid);solve(mid+1,r);
		
		int top=0;
		rep(i,l,mid) {
			Point tmp=(Point){i,dpl[i-1]+S[i-1]+(ll)i*(i-3)/2+1};
			while(top>1&&slop(sta[top-1],sta[top])<slop(sta[top],tmp)) top--;
			sta[++top]=tmp;
		}
		rep(j,mid+1,r) {
			while(top>1&&getg(sta[top].x,j)<getg(sta[top-1].x,j)) top--;
			cur[j]=getg(sta[top].x,j);
		}
		dwn(j,r,mid+1) {
			if(j!=r) cur[j]=max(cur[j],cur[j+1]);
			g[j]=max(g[j],cur[j]);
		}
		
		top=0;
		rep(j,mid+1,r) {
			Point tmp=(Point){j,dpr[j+1]-S[j]+(ll)j*(j+3)/2+1};
			while(top>1&&slop(sta[top-1],sta[top])<slop(sta[top],tmp)) top--;
			sta[++top]=tmp;
		}
		rep(i,l,mid) {
			while(top>1&&getg(i,sta[top].x)<getg(i,sta[top-1].x)) top--;
			cur[i]=getg(i,sta[top].x);
		}
		rep(i,l,mid) {
			if(i!=l) cur[i]=max(cur[i],cur[i-1]);
			g[i]=max(g[i],cur[i]);
		}
	}
}
int main() {
	n=read();
	rep(i,1,n) A[i]=read();
	pre_dp();reverse(A+1,A+n+1);
	rep(i,1,n) dpl[i]=f[i];
	pre_dp();reverse(A+1,A+n+1);
	rep(i,1,n) dpr[i]=f[n-i+1];
	rep(i,1,n) g[i]=-inf,S[i]=S[i-1]+A[i];
	solve(1,n);
	m=read();
	while(m--) {
		int x=read(),t=read();
		ll res=dpl[x-1]+dpr[x+1];
		res=max(res,g[x]+A[x]-t);
		printf("%lld\n",res);
	}
	return 0;
}

Measured memory_bytes: 21632