Language: C++

#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (300005)

using namespace std;

ll sum[N],tmp[N],f1[N],f2[N],h[N],g[N],y[N],a[N],res;
int q[N],n,m,top;

il int gi(){
  RG int x=0,q=1; RG char ch=getchar();
  while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
  if (ch=='-') q=-1,ch=getchar();
  while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q*x;
}

il ll max(RG ll a,RG ll b){ return a>b ? a : b; }

il void dp(ll *f){
  q[top=1]=0;
  for (RG int i=1;i<=n;++i){
    sum[i]=sum[i-1]+a[i],f1[i]=f1[i-1],res=(1LL*i*(i+1)>>1)-sum[i];
    while (top>1 && (y[q[top]]-y[q[top-1]])<=1LL*i*(q[top]-q[top-1])) --top;
    f[i]=max(f[i],res+y[q[top]]-1LL*i*q[top]),y[i]=f[i]+sum[i]+(1LL*i*(i-1)>>1);
    while (top>1 && (y[i]-y[q[top-1]])*(q[top]-q[top-1])>=(y[q[top]]-y[q[top-1]])*(i-q[top-1])) --top;
    q[++top]=i;
  }
  return;
}

il void solve(ll *f,ll *g,RG int l,RG int r){
  if (l==r){ h[l]=max(h[l],f[l-1]+g[l+1]-a[l]+1); return; } RG int mid=(l+r-D)>>1; top=0;
  for (RG int i=l-1;i<mid;++i){
    while (top>1 && (y[i]-y[q[top-1]])*(q[top]-q[top-1])>=(y[q[top]]-y[q[top-1]])*(i-q[top-1])) --top;
    q[++top]=i;
  }
  for (RG int i=mid;i<=r;++i){
    while (top>1 && (y[q[top]]-y[q[top-1]])<=1LL*i*(q[top]-q[top-1])) --top;
    tmp[i]=(1LL*i*(i+1)>>1)-sum[i]+y[q[top]]-1LL*i*q[top]+g[i+1];
  }
  for (RG int i=r-1;i>=mid;--i) tmp[i]=max(tmp[i],tmp[i+1]);
  for (RG int i=mid;i<=r;++i) h[i]=max(h[i],tmp[i]);
  solve(f,g,l,mid),solve(f,g,mid+1,r); return;
}

int main(){
  n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi();
  dp(f1),reverse(a+1,a+n+1),dp(f2),reverse(a+1,a+n+1),reverse(f2+1,f2+n+1);
  for (RG int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i],y[i]=f1[i]+sum[i]+(1LL*i*(i-1)>>1);
  solve(f1,f2,1,n),reverse(a+1,a+n+1),reverse(f1+1,f1+n+1),reverse(f2+1,f2+n+1),reverse(h+1,h+n+1);
  for (RG int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i],y[i]=f2[i]+sum[i]+(1LL*i*(i-1)>>1); D=1;
  solve(f2,f1,1,n),reverse(a+1,a+n+1),reverse(f1+1,f1+n+1),reverse(f2+1,f2+n+1),reverse(h+1,h+n+1),m=gi();
  while (m--){
    RG int p=gi(),x=gi();
    printf("%lld\n",max(f1[p-1]+f2[p+1],h[p]+a[p]-x));
  }
  return 0;
}


Compiler output:
a.cc: In function 'int gi()':
a.cc:13:10: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   13 |   RG int x=0,q=1; RG char ch=getchar();
      |          ^
a.cc:13:14: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   13 |   RG int x=0,q=1; RG char ch=getchar();
      |              ^
a.cc:13:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   13 |   RG int x=0,q=1; RG char ch=getchar();
      |                           ^~
a.cc: At global scope:
a.cc:20:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   20 | il ll max(RG ll a,RG ll b){ return a>b ? a : b; }
      |                 ^
a.cc:20:25: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   20 | il ll max(RG ll a,RG ll b){ return a>b ? a : b; }
      |                         ^
a.cc: In function 'void dp(long long int*)':
a.cc:24:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   24 |   for (RG int i=1;i<=n;++i){
      |               ^
a.cc: At global scope:
a.cc:34:34: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   34 | il void solve(ll *f,ll *g,RG int l,RG int r){
      |                                  ^
a.cc:34:43: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   34 | il void solve(ll *f,ll *g,RG int l,RG int r){
      |                                           ^
a.cc: In function 'void solve(long long int*, long long int*, int, int)':
a.cc:35:77: error: 'D' was not declared in this scope
   35 |   if (l==r){ h[l]=max(h[l],f[l-1]+g[l+1]-a[l]+1); return; } RG int mid=(l+r-D)>>1; top=0;
      |                                                                             ^
a.cc:35:68: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   35 |   if (l==r){ h[l]=max(h[l],f[l-1]+g[l+1]-a[l]+1); return; } RG int mid=(l+r-D)>>1; top=0;
      |                                                                    ^~~
a.cc:36:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   36 |   for (RG int i=l-1;i<mid;++i){
      |               ^
a.cc:40:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   40 |   for (RG int i=mid;i<=r;++i){
      |               ^
a.cc:44:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |   for (RG int i=r-1;i>=mid;--i) tmp[i]=max(tmp[i],tmp[i+1]);
      |               ^
a.cc:45:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   45 |   for (RG int i=mid;i<=r;++i) h[i]=max(h[i],tmp[i]);
      |               ^
a.cc: In function 'int main()':
a.cc:50:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   50 |   n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi();
      |                       ^
a.cc:52:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |   for (RG int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i],y[i]=f1[i]+sum[i]+(1LL*i*(i-1)>>1);
      |               ^
a.cc:54:15: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   54 |   for (RG int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i],y[i]=f2[i]+sum[i]+(1LL*i*(i-1)>>1); D=1;
      |               ^
a.cc:54:86: error: 'D' was not declared in this scope
   54 |   for (RG int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i],y[i]=f2[i]+sum[i]+(1LL*i*(i-1)>>1); D=1;
      |                                                                                      ^
a.cc:57:12: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   57 |     RG int p=gi(),x=gi();
      |            ^
a.cc:57:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   57 |     RG int p=gi(),x=gi();
      |                   ^