#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<lint,lint> pii;
lint INF=2e15,L[1000003],fenmax[1000003],B;
int to[1000003],u[1000003];
int ch;
lint getmax(int i){
lint ans=-INF;
while(i>0)
{
ans=max(ans,fenmax[i]);
i -= (i & -i);
}
return ans;
}
void update(int i, lint v) {
while (i <= B) {
fenmax[i] =max(fenmax[i],v);
i += (i & -i);
}
}
lint find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
for(int i=1;i<n;i++)L[i]=L[i-1]+l[i-1];
lint p,q,h,maxi,mini;
vector<pair<lint,int>>S,T;
for(int i=0;i<n;i++){
S.push_back({d[i]-L[i],i});
T.push_back({d[i]+L[i],i});
}
sort(S.begin(),S.end());
sort(T.begin(),T.end());
for(int i=0;i<n;i++){
to[S[i].second]=i;
}
B=n;
p=q=0;
maxi=-INF;
mini=-INF;
for(int i=0;i<n;i++)
{
p=max(p,d[i]+mini);
q=max(q,d[i]+L[i]+maxi);
maxi=max(maxi,d[i]-L[i]);
if(mini<d[i])mini=d[i];
}
while(p!=q-1)
{
h=(p+q)/2;
ch=0;
pii x={-INF,INF},y={-INF,INF};
for(int i=1;i<=n;i++)fenmax[i]=-INF;
int maxind=-1,ind=n;
for(int i=0;i<n;i++)
{
while(ind-1>=0 && h-T[i].first<S[ind-1].first)ind--;
u[T[i].second]=ind;
}
for(int j=0;j<n;j++)
{
int i=u[j];
if(i<=maxind)
{
maxi=getmax(n-i)-h+d[j]+c;
mini=-S[maxind].first+h-d[j]-c;
x.first=max(x.first,maxi-L[j]);
x.second=min(x.second,mini-L[j]);
y.first=max(y.first,maxi+L[j]);
y.second=min(y.second,mini+L[j]);
if(x.first>x.second || y.first>y.second)break;
}
update(n-to[j],L[j]+d[j]);
maxind=max(maxind,to[j]);
}
if(x.first<=x.second && y.first<=y.second)
{
int x0=0,x1=-1,y0=n,y1=n-1;
for(int j=0;j<n;j++)
{
while(x0<j && x.first+L[j]>L[x0])x0++;
while(x1+1<j && x.second+L[j]>=L[x1+1])x1++;
while(y0-1>=0 && y.first-L[j]<=L[y0-1])y0--;
while(y1>=0 && y.second-L[j]<L[y1])y1--;
if(x0<=x1 && y0<=y1 && x1<j && y1<j && !(x0>y1 || y0>x1))ch=1;
}
}
if(ch)q=h;
else p=h;
}
return q;
}
