#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif
const int N = 1 << 20;
const ll INF = 1e18;
ll A[N], B[N];
void init(){
fill(A, A + N, -INF);
fill(B, B + N, INF);
}
inline void add(int j, ll x, ll y){
int i = j + 1;
for(; i < N; i += i & -i)
A[i] = max(A[i], x);
for(i = j + 1; i < N; i += i & -i)
B[i] = min(B[i], y);
}
ll tempa, tempb;
void get(int j){
int i = j + 1;
tempa = -INF;
tempb = INF;
for(; i; i -= i & -i)
tempa = max(tempa, A[i]);
for(i = j + 1; i; i -= i & -i)
tempb = min(tempb, B[i]);
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
vector<ll> p(n);
for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
vector<int> perm1(n), perm2(n);
vector<int> where(n);
iota(all(perm1), 0);
iota(all(perm2), 0);
sort(all(perm1), [&](int i, int j){return d[i] - p[i] > d[j] - p[j];});
sort(all(perm2), [&](int i, int j){return d[i] + p[i] < d[j] + p[j];});
for(int i = 0; i < n; i++) where[perm1[i]] = i;
ll lo = 0, hi = 1000000000LL * 10000000LL;
vector<int> position(n);
while(lo < hi){
ll D = (lo + hi) / 2;
int cur = 0; // < 0
for(int i : perm2){
while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++;
position[i] = cur;
}
init();
ll L1 = -INF, R1 = INF, L2 = -INF, R2 = INF;
for(int j = 0; j < n; j++){
get(position[j] - 1);
L1 = max(L1, tempa + d[j] + c - p[j] - D);
R1 = min(R1, tempb - d[j] - c - p[j] + D);
L2 = max(L2, tempa + p[j] - D + d[j] + c);
R2 = min(R2, tempb + p[j] + D - d[j] - c);
add(where[j], p[j] + d[j], p[j] - d[j]);
}
if(L1 > R1 || L2 > R2){
lo = D + 1;
continue;
}
// some u, v with p[u] - p[v] in [L1, R1] and p[u] + p[v] in [L2, R2]
bool ok = false;
int ptr1 = 0; // first >= p[v] + L1
int ptr2 = n; // first >= L2 - p[v];
for(int v = 1; v < n; v++){
ll L = max(p[v] + L1, L2 - p[v]);
ll R = min(p[v] + R1, R2 - p[v]);
// in L, R?
// int u = upper_bound(all(p), L - 1) - p.begin(); // first >= L
while(ptr1 < n && p[ptr1] < L1 + p[v]) ptr1++;
while(ptr2 > 0 && p[ptr2 - 1] >= L2 - p[v]) ptr2--;
int u = max(ptr1, ptr2);
if(u >= v) continue;
if(p[u] > R) continue;
ok = true;
break;
}
if(ok) hi = D;
else lo = D + 1;
}
return lo;
}
