#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
long long sum[300010];
int idx1,idx2;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
for(int i=1;i<n;i++)
sum[i] = sum[i-1] + l[i-1];
long long left = 0 , right = 1e18;
long long ans = 0;
long long mx = d[0];
int last = 0 ;
idx1 = 0;
for(int i=1;i<n;i++){
long long dis = sum[i] - sum[last] +d[i] + d[last] ;
if(dis > mx){
mx = dis ;
idx1 = last;
idx2 = i ;
}
if(d[i] > sum[i] - sum[last] + d[last])
last = i ;
}
right = mx;
ans = mx;
last =0 ;
mx = d[0] ;
for(int i=1;i<=idx1;i++){
long long dis = sum[i] - sum[last] + d[i] + d[last];
if(dis > mx){
mx = dis;
}
if(d[i] > sum[i] - sum[last] + d[last])
last = i;
}
last = idx2;
mx = max(mx,(long long)d[last]);
for(int i=idx2+1;i<n;i++){
long long dis = sum[i] - sum[last] + d[i] + d[last];
if(dis > mx){
mx = dis;
}
if(d[i] > sum[i] - sum[last] + d[last])
last = i;
}
left = mx;
while(right >= left){
long long mid=(left+right)/2;
long long mx1 = 0 ;
int idx3 = idx1;
long long mx2= 0;
int idx4 = idx2;
for(int i=idx1+1;i<idx2;i++){
long long dis = sum[i] - sum[idx1] + d[i] + d[idx1];
long long dis2 = sum[idx2] - sum[i] + d[idx2] + d[i];
if(dis > mid){
if(dis2 > mx2)
{
mx2 = dis2 ;
idx4= i ;
}
}
if(dis2 > mid){
if(dis > mx1){
mx1 = dis ;
idx3 = i;
}
}
}
bool can = 1 ;
int idx5 = idx1;
int idx6 = idx2;
long long mn = 1e18;
for(int i=idx1;i<=idx3;i++){
long long dis = max((long long)(sum[i] - sum[idx1] + (long long)d[idx1]),(long long)(sum[idx3] - sum[i] + (long long)d[idx3])) + (long long)c + d[idx2];
if(dis > mid)
continue;
long long cur = mid - dis;
int j = lower_bound(sum,sum+n,sum[idx2]-cur) - sum;
if(j < idx4)
j = idx4;
long long dis2 = sum[i] - sum[idx1] + d[idx1] + c + sum[j] - sum[idx4] + d[idx4];
if(dis2 > mid)
continue;
long long dis4 = sum[idx3] - sum[i] + sum[j] - sum[idx4];
if(dis4 < mn){
mn = dis4;
idx5 = i;
idx6 = j;
}
}
long long dis = max(sum[idx5] - sum[idx1] + d[idx1],sum[idx3] - sum[idx5] + d[idx3]) + c + sum[idx2] - sum[idx6] + d[idx2];
if(dis > mid)
can = false;
long long dis2 = max(sum[idx2] - sum[idx6] + d[idx2],sum[idx6] - sum[idx4] + d[idx4]) + c + sum[idx5] - sum[idx1] + d[idx1];
if(dis2 > mid)
can = false;
vector< pair<long long,long long> > v1,v2;
for(int i=idx5;i<=idx3;i++)
v1.push_back(make_pair(sum[i] - sum[idx5] + d[i],sum[idx3] - sum[i] + d[i]));
for(int i=idx4;i<=idx6;i++)
v2.push_back(make_pair(sum[idx6] - sum[i] + d[i],sum[i] - sum[idx4] + d[i]));
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
long long best = -1e18 ;
int j = 0 ;
for(int i=v2.size()-1;i>=0;i--){
while(j < (int)v1.size() && v1[j].first+v2[i].first+c <= mid){
if(v1[j].second+best + sum[idx4] - sum[idx3] > mid)
can = false;
j++;
}
best = max(best,v2[i].second);
}
while(j <(int)v1.size()){
if(v1[j].second+best + sum[idx4] - sum[idx3] > mid)
can = false;
j++;
}
if(can){
ans = mid;
right = mid - 1;
}
else
left = mid + 1;
}
return ans;
}
