#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
const int maxn = int(1e6) + 10;
const ll inf = ll(4e15);
int n; ll L;
ll P[maxn], D[maxn], A[maxn], B[maxn];
const int M = 1048576;
pll sortedBwithIdx[maxn];
ll sortedB[maxn];
int sortedBrev[maxn];
pll emax(pll a, pll b) { return {max(a.first, b.first), max(a.second, b.second)}; }
pll tree[M<<1];
char timestamp[M<<1]; char nowt;
pll range_max(int l, int r) {
pll ans(-inf, -inf);
for (l+=M, r+=M; l<=r; l/=2, r/=2) {
if (l%2 == 1) {
if (timestamp[l] == nowt) ans = emax(ans, tree[l]);
++l;
}
if (r%2 == 0) {
if (timestamp[r] == nowt) ans = emax(ans, tree[r]);
--r;
}
}
return ans;
}
bool can_satisfy(ll V) {
ll plus_min = -inf, plus_max = inf;
ll minus_min = -inf, minus_max = inf;
++nowt;
for (int j=0; j<n; ++j) {
auto [maxAi, maxBi] = range_max(
int(upper_bound(sortedB, sortedB+n, V-A[j])-sortedB),
n-1);
plus_min = max(plus_min, maxAi + A[j] - V + L);
plus_max = min(plus_max, V - L - maxBi - B[j]);
minus_min = max(minus_min, maxAi + B[j] - V + L);
minus_max = min(minus_max, V - L - maxBi - A[j]);
{ int p = M+sortedBrev[j]; tree[p] = {A[j], B[j]}; timestamp[p] = nowt;
for (p/=2; p; p/=2) {
if (timestamp[p*2] != nowt) tree[p*2] = {-inf, -inf}, timestamp[p*2] = nowt;
if (timestamp[p*2+1] != nowt) tree[p*2+1] = {-inf, -inf}, timestamp[p*2+1] = nowt;
tree[p] = emax(tree[p*2], tree[p*2+1]);
timestamp[p] = nowt;
} }
}
set<ll> px;
for (int y=0; y<n; ++y) {
ll pxmin = max(plus_min - P[y], minus_min + P[y]);
ll pxmax = min(plus_max - P[y], minus_max + P[y]);
auto it = px.lower_bound(pxmin);
if (it != px.end() && (*it) <= pxmax) return true;
px.insert(P[y]);
}
return false;
}
void prepare() {
for (int i=0; i<n; ++i) sortedBwithIdx[i] = {B[i], i};
sort(sortedBwithIdx, sortedBwithIdx+n);
for (int i=0; i<n; ++i) {
sortedBrev[sortedBwithIdx[i].second] = i;
sortedB[i] = sortedBwithIdx[i].first;
}
}
ll find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
n = n_; L = c;
copy(d.begin(), d.end(), D);
for (int i=1; i<n; ++i) P[i] = P[i-1] + l[i-1];
for (int i=0; i<n; ++i) A[i] = D[i] + P[i], B[i] = D[i] - P[i];
prepare();
ll left = 0, right = inf;
while (left + 1 < right) {
ll md = (left + right) / 2;
(can_satisfy(md) ? right : left) = md;
}
return right;
}
