#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define fs first
#define sc second
long long find_shortcut(int n, std::vector<int> L, std::vector<int> D, int C)
{
ll l[n],d[n];
for(int i=0;i<n-1;i++)l[i]=L[i];
l[n-1]=0;
for(int i=0;i<n;i++)d[i]=D[i];
ll c=C;
ll c1[n],c2[n];
c1[0]=d[0];
for(int i=1;i<n;i++)c1[i]=max(c1[i-1]+l[i-1],d[i]);
c2[n-1]=d[n-1];
for(int i=n-2;i>-1;i--)c2[i]=max(c2[i+1]+l[i],d[i]);
ll m1[n],m2[n];
m1[0]=d[0];
for(int i=1;i<n;i++)m1[i]=max(m1[i-1],d[i]+l[i-1]+c1[i-1]);
m2[n-1]=d[n-1];
for(int i=n-2;i>-1;i--)m2[i]=max(m2[i+1],d[i]+l[i]+c2[i+1]);
auto clc=[&](int x,int y){
ll dx=d[x],dy=d[y],ly=l[y];
d[x]=c1[x];
d[y]=c2[y];
l[y]=c;
ll s=0;
for(int i=x;i<=y;i++)s+=l[i];
s/=2;
deque<pll> dq;
dq.pb({x,d[x]});
ll mx=max(m1[x],m2[y]);
for(ll i=x,j=x,pi=0,pj=0;i<=y;i++){
while(pj+l[j]-pi<=s){
pj+=l[j];
j++;
if(j>y)j=x;
ll t=pj+d[j];
while(!dq.empty()&&dq.back().sc<t)dq.pop_back();
dq.pb({j,t});
}
if(dq.front().fs==i)dq.pop_front();
if(!dq.empty()){
mx=max(mx,dq[0].sc-pi+d[i]);
}
pi+=l[i];
}
d[x]=dx;
d[y]=dy;
l[y]=ly;
return mx;
};
ll ans=1e18;
for(int x=0;x<n-1;x++){
int l=x+1,r=n-1;
while(l<r){
int m=l+r>>1;
if(clc(x,m)<clc(x,m+1))r=m;
else l=m+1;
}
ans=min(ans,clc(x,l));
}
return ans;
}
