#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=300005;
LL f[MAXN],g[MAXN],pres[MAXN],T[MAXN];
LL presA[MAXN],presB[MAXN];
int n,m;
int li[MAXN],hd,tl;
double getC(int x,LL *A){return A[x]+1LL*x*(x-1)/2+pres[x];}
double getx(int k1,int k2,LL *A){return (getC(k2,A)-getC(k1,A))/((double)k2-k1);}
void getf(int N,LL *A)
{
	for(int i=0;i<=N;i++)A[i]=0;
	hd=tl=1;li[1]=0;
	for(int i=1;i<=N;i++)
	{
		while(hd<tl&&getx(li[tl-1],li[tl],A)<=i)--tl;assert(hd<=tl);
		A[i]=A[li[tl]]+1LL*(i-li[tl]+1)*(i-li[tl])/2-pres[i]+pres[li[tl]];
		chkmax(A[i],A[i-1]);
		while(hd<tl&&getx(li[tl-1],li[tl],A)<=getx(li[tl-1],i,A))--tl;
		li[++tl]=i;
	}
}
void getconvex(int l,int r,LL *A)
{
	hd=tl=1;li[1]=l;
	for(int i=l+1;i<=r;i++)
	{
		while(hd<tl&&getx(li[tl-1],li[tl],A)<=i)--tl;
		while(hd<tl&&getx(li[tl-1],li[tl],A)<=getx(li[tl-1],i,A))--tl;
		li[++tl]=i;
	}
}
LL with[MAXN],value[MAXN],INF;
void solve(int l,int r)
{
	if(l>r)return ;int mid=(l+r)/2;
	for(int i=l-1;i<=r;i++)pres[i]=presA[i];getconvex(l-1,mid-1,f);
	for(int i=mid,p=tl;i<=r;i++)
	{
		while(hd<p&&getx(li[p-1],li[p],f)<=i)--p;
		value[i]=g[n-(i+1)+1]+f[li[p]]+1LL*(i-li[p]+1)*(i-li[p])/2-pres[i]+pres[li[p]];
	}
	for(int i=r;i>=mid;i--)
	{
		if(i!=r)chkmax(value[i],value[i+1]);
		chkmax(with[i],value[i]);
	}
	for(int i=n-r;i<=n-l+1;i++)pres[i]=presB[i];getconvex(n-r,n-mid,g);
	for(int i=mid,p=tl;i>=l;i--)
	{
		while(hd<p&&getx(li[p-1],li[p],f)<=n-i+1)--p;
		value[i]=f[i-1]+g[li[p]]+1LL*((n-i+1)-li[p]+1)*((n-i+1)-li[p])/2-pres[n-i+1]+pres[li[p]];
	}
	for(int i=l;i<=mid;i++)
	{
		if(i!=l)chkmax(value[i],value[i-1]);
		chkmax(with[i],value[i]);
	}
	solve(l,mid-1);
	solve(mid+1,r);
}
int main()
{
	n=read();for(int i=1;i<=n;i++)T[i]=read();
	for(int i=1;i<=n;i++)presA[i]=T[i],presA[i]+=presA[i-1];
	for(int i=1;i<=n;i++)pres[i]=presA[i];getf(n,f);
	for(int i=1;i<=n;i++)presB[i]=T[n-i+1],presB[i]+=presB[i-1];
	for(int i=1;i<=n;i++)pres[i]=presB[i];getf(n,g);
	memset(with,-63,sizeof(with));INF=with[0];solve(1,n);
	m=read();
	while(m--)
	{
		int x=read(),v=read();pres[0]=0;
//		for(int i=1;i<=n;i++)pres[i]=(n-i+1==x?v:T[n-i+1]),pres[i]+=pres[i-1];getf(n,g);
//		pr2(g[n]);
		pr2(max(f[x-1]+g[n-x],with[x]+T[x]-v));
	}
	return 0;
}



Measured memory_bytes: 22528