#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

int isbetter(pll a,pll b,pll c){
  if(c.X<a.X){
    swap(a,c);
  }
  return ((long double)b.Y-c.Y)*(c.X-a.X)<=((long double)a.Y-c.Y)*(c.X-b.X);
  
}
ll tk[N],sum[N];
ll dpf[N],dpr[N],incl[N],tp[N];
ll eval(pll a,ll b){
  return a.X*b+a.Y;
}
void solve(int st,int ed){
  if(ed<st) return;
  int m=(st+ed)/2;
  vector<pll> qw;
  REPP(i,max(st-1,0),m){
    pll z = mp(-i,dpf[i]+1ll*i*(i-1)/2+sum[i]);
    while(qw.size()>1&&isbetter(qw[qw.size()-2],qw.back(),z)) qw.pop_back();
    qw.pb(z);
  }
  ll z=-INF;
  if(qw.size()){
    REPP(i,m+1,ed+1){
      while(qw.size()>1&&eval(qw.back(),i)<=eval(qw[qw.size()-2],i)) qw.pop_back();
      tp[i]=eval(qw.back(),i)+1ll*i*(i+1)/2-sum[i];
    }
    
    for(int i=ed;i>m;i--) {
      z=max(z,tp[i]+dpr[i]);
      incl[i]=max(z,incl[i]);
    }
  }
  qw.clear();
  int tl=0;
  for(int i=ed;i>=m;i--){
    pll z=mp(-i,dpr[i]+1ll*i*(i+1)/2-sum[i]);
    while(qw.size()>tl+1&&isbetter(qw[qw.size()-2],qw.back(),z)) qw.pop_back();
    qw.pb(z);
   // printf("g%d %lld\n",i,dpr[i]);

  }
  for(int i=m-1;i>=max(st-1,0);i--){
    while(qw.size()>1&&eval(qw.back(),i)<=eval(qw[qw.size()-2],i)) qw.pop_back();
    tp[i]=eval(qw.back(),i)+1ll*i*(i-1)/2+sum[i];
  }
  z=-INF;
  REPP(i,max(0,st-1),m+1){
    incl[i]=max(z,incl[i]);
    z=max(z,tp[i]+dpf[i]);
  }
  // printf("%d %d %d\n",st,m,ed);
  // REPP(i,st,ed+1) printf("%d %lld\n",i,incl[i]);
  solve(st,m-1); solve(m+1,ed);
}
int main(){
  int n; scanf("%d",&n);
  incl[0]=-INF;
  REP(i,n) scanf("%lld",&tk[i+1]),sum[i+1]=sum[i]+tk[i+1],incl[i+1]=-INF;
  dpf[0]=0;
  vector<pll> qw;
  qw.pb(mp(0,0));
  REPP(i,1,n+1){
    while(qw.size()>1&&eval(qw.back(),i)<=eval(qw[qw.size()-2],i)) qw.pop_back();
    dpf[i]=max(dpf[i-1],eval(qw.back(),i)+1ll*i*(i+1)/2-sum[i]);
    pll z = mp(-i,dpf[i]+1ll*i*(i-1)/2+sum[i]);
    while(qw.size()>1&&isbetter(qw[qw.size()-2],qw.back(),z)) qw.pop_back();
    qw.pb(z);
    //printf("g%d %lld\n",i,dpf[i]);
  }
  qw.clear();
  int tl=0;
  for(int i=n;i>=0;i--){
    if(i==n) dpr[i]=0;
    else{
      //while(tl+1<qw.size()&&eval(qw[tl],i)<=eval(qw[tl+1],i)) tl++;
      while(qw.size()>1&&eval(qw.back(),i)<=eval(qw[qw.size()-2],i)) qw.pop_back();
      dpr[i]=max(dpr[i+1],eval(qw.back(),i)+1ll*i*(i-1)/2+sum[i]); //ggg start here 
    }
    //if(tl<qw.size()) printf("%lld %lld %lld %lld %d\n",qw.back().X,qw.back().Y,qw[qw.size()-2].X,qw[qw.size()-2].Y,(int)qw.size());
    pll z=mp(-i,dpr[i]+1ll*i*(i+1)/2-sum[i]);
    while(qw.size()>tl+1&&isbetter(qw[qw.size()-2],qw.back(),z)) qw.pop_back();
    qw.pb(z);
    
    //printf("g%d %lld\n",i,dpr[i]);

  }
  solve(0,n);
  int qq; scanf("%d",&qq);
  while(qq--){
    int pl ,val; scanf("%d%d",&pl,&val);
    ll ans=max(incl[pl]-val+tk[pl],dpf[pl-1]+dpr[pl]);
  //  printf("%lld %lld\n",incl[pl],dpf[pl-1]+dpr[pl]);
    printf("%lld\n",ans);
  }
  return 0;
}

Measured memory_bytes: 16640