#include <bits/stdc++.h>
#include "shortcut.h"
using ll = long long;
constexpr ll inf = std::numeric_limits<ll>::max() / 2;
using std::vector;
using std::array;
using std::pair;
using std::tuple;
ll find_shortcut(int N, vector<int> L, vector<int> D, int C) {
vector<ll> X(N);
for (int i = 0; i < N - 1; ++i) {
X[i + 1] = X[i] + L[i];
}
vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
return X[i] + D[i] < X[j] + D[j];
});
vector<pair<ll, int>> sum(N);
vector<tuple<ll, ll, int>> dif(N + 1);
dif[N] = {inf, inf, -1};
for (int i = N - 1; i >= 0; --i) {
const int k = ord[i];
sum[i] = {X[k] + D[k], k};
if (X[k] - D[k] < std::get<0>(dif[i + 1])) {
dif[i] = {X[k] - D[k], std::get<0>(dif[i + 1]), k};
} else {
dif[i] = dif[i + 1];
std::get<1>(dif[i]) = std::min(std::get<1>(dif[i]), X[k] - D[k]);
}
}
std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
return X[i] - D[i] < X[j] - D[j];
});
vector<int> lowb(N);
const auto check = [&](const ll thres) {
ll a = -inf, b = inf, c = -inf, d = inf;
int upb = 0;
for (const int i : ord) {
while (upb < N and sum[upb].first <= thres + X[i] - D[i]) upb += 1;
if (upb == N) continue;
if (upb == N - 1 and sum[upb].second == i) continue;
const ll max_sum = sum[N - 1].second == i ? sum[N - 2].first : sum[N - 1].first;
a = std::max(a, max_sum + X[i] + D[i] + C - thres);
c = std::max(c, max_sum - X[i] + D[i] + C - thres);
const ll min_dif = std::get<2>(dif[upb]) == i ? std::get<1>(dif[upb]) : std::get<0>(dif[upb]);
b = std::min(b, min_dif + X[i] - D[i] - C + thres);
d = std::min(d, min_dif - X[i] - D[i] - C + thres);
}
int idx = 0;
for (int i = N - 1; i >= 0; --i) {
while (idx < N and X[idx] < a - X[i]) idx += 1;
lowb[i] = idx;
}
idx = 0;
for (int i = 0; i < N; ++i) {
while (idx < N and X[idx] < c + X[i]) idx += 1;
const int k = std::max(lowb[i], idx);
if (k < N and X[k] <= std::min(b - X[i], d + X[i])) return true;
}
return false;
};
ll ok = inf, ng = 0;
while (ok - ng > 1) {
const ll md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
return ok;
}
