#include<bits/stdc++.h>
#include "shortcut.h"
#define fi first
#define se second
using namespace std;
const int N=1e6;
const long long INF=1e16;
int all_mx;
int w[N+10];
int dd[N+10];
long long pref[N+10];
long long tab[N+10][2];
pair<long long,int> srt[2][N+10];
long long bst[2][N+10]; //0-sum, 1-difference
long long pp[2][N+10];
long long ss[2][N+10];
long long ll[N+10];
long long rr[N+10];
bool ok(int n,int c,long long x)
{
int i,j;
long long mx[2]={-INF,-INF};
for(i=1,j=n;i<=n;i++)
{
while(j>0 && srt[0][j].fi+srt[1][i].fi>x)
{
int v=srt[0][j].se;
mx[0]=max(mx[0],w[v]+pref[v]);
mx[1]=max(mx[1],w[v]-pref[v]);
j--;
}
int v=srt[1][i].se;
bst[0][v]=mx[0];
bst[1][v]=mx[1];
}
bst[0][all_mx]=bst[1][all_mx]=-INF;
for(i=all_mx+1;i<=n;i++)
{
if(w[i]+pref[i]-pref[all_mx]+w[all_mx]>x)
{
bst[0][all_mx]=max(bst[0][all_mx],w[i]+pref[i]);
bst[1][all_mx]=max(bst[1][all_mx],w[i]-pref[i]);
}
}
pp[0][0]=pp[1][0]=-INF;
for(i=1;i<=n;i++)
{
pp[0][i]=max(pp[0][i-1],w[i]-pref[i]+bst[0][i]);
pp[1][i]=max(pp[1][i-1],w[i]-pref[i]+bst[1][i]);
}
ss[0][n+1]=ss[1][n+1]=-INF;
for(i=n;i>=1;i--)
{
ss[0][i]=max(ss[0][i+1],w[i]+pref[i]+bst[0][i]);
ss[1][i]=max(ss[1][i+1],w[i]+pref[i]+bst[1][i]);
}
for(i=1;i<=n;i++)
{
ll[i]=max(pp[0][i]+pref[i]+c-x,ss[0][i]+c-pref[i]-x);
rr[i]=min(x-pp[1][i]-pref[i]-c,x-ss[1][i]-c+pref[i]);
}
for(int it:{0,1})
{
j=n;
for(i=1;i<=n;i++)
{
while(j>1 && pref[j-1]>=ll[i])
j--;
if(ll[i]<=pref[j] && pref[j]<=rr[i])
return true;
}
reverse(ll+1,ll+n+1);
reverse(rr+1,rr+n+1);
}
return false;
}
long long find_shortcut(int n,vector<int> l,vector<int> d,int c)
{
for(int i=0;i<n;i++)
w[i+1]=d[i];
for(int i=0;i<n-1;i++)
dd[i+2]=l[i];
for(int i=1;i<=n;i++)
pref[i]=pref[i-1]+dd[i];
for(int i=1;i<=n;i++)
{
srt[0][i]={w[i]+pref[i],i};
srt[1][i]={w[i]-pref[i],i};
}
sort(srt[0]+1,srt[0]+n+1);
sort(srt[1]+1,srt[1]+n+1);
int mx[2]={0,0};
for(int i=1;i<=n;i++)
{
if(w[i]>mx[0])
{
mx[1]=mx[0];
mx[0]=w[i];
all_mx=i;
}
else if(w[i]>mx[1])
mx[1]=w[i];
}
long long bg,en,mid;
bg=mx[0]+mx[1];
en=1e16;
while(bg<en)
{
mid=(bg+en)/2;
if(ok(n,c,mid))
en=mid;
else
bg=mid+1;
}
return bg;
}
