#include "shortcut.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
const i64 PINF = numeric_limits<i64>::max();
const i64 NINF = numeric_limits<i64>::min();
class segTree {
public:
vector<i64> vl;
int N;
segTree() = default;
segTree(int _N) {
vl.resize(1 << 18, PINF);
N = _N;
}
void update(int s, int e, int n, int t, i64 ne) {
if (s == e) {
vl[n] = ne;
return;
}
int m = (s + e) >> 1;
int k = n << 1;
if (t <= m)
update(s, m, k, t, ne);
else
update(m + 1, e, k + 1, t, ne);
vl[n] = min(vl[k], vl[k + 1]);
}
void update(int t, i64 ne) { update(1, N, 1, t, ne); }
i64 query(int s, int e, int n, int l, int r) {
if (r < s || e < l) return PINF;
if (l <= s && e <= r) return vl[n];
int m = (s + e) >> 1;
int k = n << 1;
return min(query(s, m, k, l, r), query(m + 1, e, k + 1, l, r));
}
i64 query(int l, int r) { return query(1, N, 1, l, r); }
};
namespace Helper {
bool inRange(int x, int s, int e) { return s <= x && x <= e; }
template <typename T>
int findIndex(const vector<T> &vec, T &&toFind) {
return upper_bound(iterall(vec), toFind) - vec.begin();
}
template <typename T>
int findIndex(const vector<T> &vec, const T &toFind) {
return upper_bound(iterall(vec), toFind) - vec.begin();
}
template <typename T>
void setmin(T &target, T &&x) {
target = min(target, x);
}
template <typename T>
void setmin(T &target, const T &x) {
target = min(target, x);
}
template <typename T>
void setmax(T &target, T &&x) {
target = max(target, x);
}
template <typename T>
void setmax(T &target, const T &x) {
target = max(target, x);
}
} // namespace Helper
i64 find_shortcut(const int N, vector<int> l, vector<int> d, int c) {
// preprocessing
vector<i64> X(N);
for (int i = 1; i < N; i++) X[i] = X[i - 1] + l[i - 1];
vector<i64> x = X;
vector<i64> D;
copy(iterall(d), back_inserter(D));
vector<pli> XD(N);
for (int i = 0; i < N; i++) XD[i] = {X[i] + D[i], i};
sort(iterall(XD));
vector<int> mp(N);
for (int i = 0; i < N; i++) mp[XD[i].second] = i;
vector<i64> xds(N);
for (int i = 0; i < N; i++) xds[i] = XD[i].first;
i64 S = c;
i64 s = 0, e = X.back() + *max_element(iterall(D)) * 2;
auto sT = segTree(N);
set<int> xpdSet;
while (s < e) {
// (r-l)Low, (r-l)High, (r+l)Low, (r+l)High
vector<i64> bounds = {NINF, PINF, NINF, PINF};
i64 m = (s + e) >> 1;
i64 mms = m - S;
// cout << m << endl;
i64 curMax = NINF;
for (int i = N - 1; i >= 0; i--) {
i64 xmd = X[i] - D[i];
i64 xpd = X[i] + D[i];
auto lidx = Helper::findIndex(xds, m + xmd);
auto lit = xpdSet.lower_bound(lidx);
if (lit == xpdSet.end()) {
xpdSet.emplace(mp[i]);
sT.update(mp[i] + 1, xmd);
curMax = max(curMax, xpd);
continue;
}
lidx = *lit;
i64 XmDmin = sT.query(lidx + 1, N);
// cout << lit->second << " " << m + X[i] - D[i] << " " << XmDmin
// << endl;
Helper::setmax(bounds[0], -mms - xmd + curMax);
Helper::setmin(bounds[1], mms - xpd + XmDmin);
Helper::setmax(bounds[2], -mms + xpd + curMax);
Helper::setmin(bounds[3], mms + xmd + XmDmin);
xpdSet.emplace(mp[i]);
sT.update(mp[i] + 1, xmd);
curMax = max(curMax, xpd);
if (bounds[0] > bounds[1] || bounds[2] > bounds[3]) break;
}
// cout << bounds[0] << " " << bounds[1] << " " << bounds[2] << " "
// << bounds[3] << endl;
xpdSet.clear();
fill(iterall(sT.vl), PINF);
bool condition = false;
for (int i = 0; i < N; i++) {
i64 L = x[i];
i64 lowBound = max(bounds[0] + L, bounds[2] - L);
i64 uppBound = min(bounds[1] + L, bounds[3] - L);
if (lowBound > uppBound) continue;
auto itl = lower_bound(iterall(x), lowBound);
auto itr = upper_bound(iterall(x), uppBound);
if (itr == x.begin()) continue;
if (itl == x.end()) continue;
if (itl != itr) {
// cout << i << " " << itl - x.begin() << endl;
condition = true;
break;
}
}
if (condition)
e = m;
else
s = m + 1;
}
return s;
}
