#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1e17;
struct Square{
ll lm, um, lp, up;
Square(){lm = lp = -INF, um = -1, up = INF;}
void update(ll x, ll y, ll r){
lm = max(lm, x-y-r);
um = min(um, x-y+r);
lp = max(lp, x+y-r);
up = min(up, x+y+r);
}
void update(ll x, ll r, Square &S){
lm = max(lm, x-r + S.lm);
um = min(um, x+r + S.um);
lp = max(lp, x-r + S.lp);
up = min(up, x+r + S.up);
}
bool valid(){return lm <= um && lp <= up;}
};
int n, I1[1001000], I2[1001000], chk[1001000];
ll X[1001000], a[1001000], c[1001000], d;
vector<int> L, R;
vector<pair<ll, ll>> ran;
bool ok(ll MX){
fill(chk, chk+n+1, 0);
ll mx = -INF;
L.clear(); R.clear();
for (int i=1;i<=n;i++){
if (mx + X[i] + c[i] > MX) chk[i] |= 2;
mx = max(mx, - X[i] + c[i]);
}
mx = -INF;
for (int i=n;i;i--){
if (mx - X[i] + c[i] > MX) chk[i] |= 1;
if (chk[i]==3) return 0;
mx = max(mx, X[i] + c[i]);
}
for (int i=1;i<=n;i++) if (chk[I1[i]]&1) L.push_back(I1[i]);
for (int i=1;i<=n;i++) if (chk[I2[i]]&2) R.push_back(I2[i]);
if (L.empty()) return 1;
int b = *max_element(L.begin(), L.end());
for (auto &i:L) a[i] = c[i] + (X[b] - X[i]);
for (auto &j:R) a[j] = c[j] + (X[j] - X[b]);
int pt = 0;
Square s, js;
for (auto &i:L){
while(pt<(int)R.size() && a[i] + a[R[pt]] > MX){
js.update(0, X[R[pt]], -c[R[pt]]);
pt++;
}
s.update(X[i], MX - c[i] - d, js);
if (!s.valid()) return 0;
}
ran.clear();
for (int i=1;i<=n;i++){
ran.emplace_back(max(s.lp-X[i], X[i]-s.um), min(s.up-X[i], X[i]-s.lm));
if (ran.back().first > ran.back().second) ran.pop_back();
}
if (ran.empty()) return 0;
for (int i=0;i<(int)ran.size();i++) if ((i==(int)ran.size()-1) || ran[i].first < ran[i+1].first){
reverse(ran.begin(), ran.begin()+i+1);
inplace_merge(ran.begin(), ran.begin()+i+1, ran.end());
break;
}
ll ss = 0, ee = 0;
pt = 2;
for (auto &[l, r]:ran){
if (l <= ee) {ee = max(ee, r); continue;}
while(pt<=n && X[pt] <= ee){
if (X[pt] >= ss) return 1;
++pt;
}
ss = l, ee = r;
}
while(pt<=n && X[pt] <= ee){
if (X[pt] >= ss) return 1;
++pt;
}
return 0;
}
bool cmp1(int i, int j){return -X[i]+c[i] < -X[j]+c[j];}
bool cmp2(int i, int j){return X[i]+c[i] > X[j]+c[j];}
ll naive(int N, std::vector<int> L, std::vector<int> D, int C){
ll ans = INF;
for (int i=1;i<N;i++) X[i] = X[i-1] + L[i-1];
for (int i=0;i<N;i++){
for (int j=i+1;j<N;j++){
ll mx = *max_element(D.begin(), D.end());
for (int s=0;s<N;s++){
for (int e=s+1;e<N;e++){
mx = max(mx, min(X[e] - X[s], min(abs(X[j]-X[e]) + abs(X[i]-X[s]) + C, abs(X[j]-X[s]) + abs(X[i] - X[e]) + C)) + D[s] + D[e]);
}
}
ans = min(ans, mx);
}
}
return ans;
}
long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int C){
//ll rans = naive(N, L, D, C);
L.reserve(N+100);
R.reserve(N+100);
ran.reserve(N+100);
n = N;
X[1] = 0;
for (int i=1;i<=n;i++) c[i] = D[i-1];
for (int i=2;i<=n;i++) X[i] = X[i-1] + L[i-2];
d = C;
for (int i=1;i<=n;i++) I1[i] = i, I2[i] = i;
sort(I1+1, I1+n+1, cmp1);
sort(I2+1, I2+n+1, cmp2);
ll l = *max_element(c+1, c+n+1), r = 1e15 + 100, ans = 1e15 + 100;
while(l<=r){
ll mid = (l+r)/2;
if (ok(mid)) r = mid-1, ans = mid;
else l = mid+1;
}
//printf("Answer: %lld\n", rans);
//printf("Output: %lld\n", ans);
//assert(ans == rans);
return ans;
}
