#include <bits/stdc++.h>
#include "shortcut.h"
template <class T>
using Vec = std::vector<T>;
using ll = long long;
constexpr ll INF = std::numeric_limits<ll>::max() / 2;
template <class T> void setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
}
}
template <class T> void setmax(T& lhs, const T& rhs) {
if (lhs < rhs) {
lhs = rhs;
}
}
template <class T> struct RMQ {
int size;
Vec<T> min;
RMQ(const int n): size(n), min(2 * n, std::numeric_limits<T>::max()) {}
void chmin(int i, const T& x) {
i += size;
setmin(min[i], x);
while (i > 1) {
i >>= 1;
setmin(min[i], min[2 * i]);
setmin(min[i], min[2 * i + 1]);
}
}
T fold(int l, int r) const {
l += size;
r += size;
T ret = std::numeric_limits<T>::max();
while (l < r) {
if (l & 1) setmin(ret, min[l++]);
if (r & 1) setmin(ret, min[--r]);
l >>= 1;
r >>= 1;
}
return ret;
}
};
ll find_shortcut(int n, Vec<int> l, Vec<int> d, int c) {
Vec<ll> x(n);
for (int i = 1; i < n; ++i) {
x[i] = x[i - 1] + l[i - 1];
}
Vec<ll> cmp(n);
for (int i = 0; i < n; ++i) {
cmp[i] = d[i] - x[i];
}
std::sort(cmp.begin(), cmp.end());
cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
Vec<int> idx(n);
for (int i = 0; i < n; ++i) {
idx[i] = std::lower_bound(cmp.begin(), cmp.end(), d[i] - x[i]) - cmp.begin();
}
const int len = (int) cmp.size();
const auto check = [&](const ll threshold) -> bool {
ll sum_min = -INF, sum_max = INF;
ll dif_min = -INF, dif_max = INF;
RMQ<ll> min1(len), min2(len);
for (int i = 0; i < n; ++i) {
const int pos = std::upper_bound(cmp.begin(), cmp.end(), threshold - (x[i] + d[i])) - cmp.begin();
const ll a = min1.fold(pos, len);
const ll b = min2.fold(pos, len);
if (a != std::numeric_limits<ll>::max()) {
setmin(sum_max, a + (x[i] - d[i]) + threshold - c);
setmax(sum_min, -b + (x[i] + d[i]) + c - threshold);
setmin(dif_max, b + (x[i] - d[i]) + threshold - c);
setmax(dif_min, -a + (x[i] + d[i]) + c - threshold);
}
min1.chmin(idx[i], x[i] - d[i]);
min2.chmin(idx[i], -(x[i] + d[i]));
}
if (sum_min > sum_max or dif_min > dif_max) {
return false;
}
// int s = 0, t = 0, u = 0, v = 0;
// for (int i = 0; i < n; ++i) {
// while (s < n and x[s] <= sum_max - x[i]) s += 1;
// while (t < n and x[t] < sum_min - x[i]) t += 1;
// while (u < n and x[u] <= dif_max + x[i]) u += 1;
// while (v < n and x[v] < dif_min + x[i]) v += 1;
// if (std::max({t, v, i + 1}) < std::min(s, u)) {
// return true;
// }
// }
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (sum_min <= x[i] + x[j] and x[i] + x[j] <= sum_max and dif_min <= x[j] - x[i] and x[j] - x[i] <= dif_max) {
return true;
}
}
}
return false;
};
ll ok = INF, ng = 0;
while (ok - ng > 1) {
const auto md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
return ok;
}
