#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> XpD(N);
for (int i = 0; i < N; i++) XpD[i] = {X[i] + D[i], i};
sort(iterall(XpD));
vector<int> mpp(N);
for (int i = 0; i < N; i++) mpp[XpD[i].second] = i;
vector<pli> XmD(N);
for (int i = 0; i < N; i++) XmD[i] = {X[i] - D[i], i};
sort(iterall(XmD));
vector<int> mpm(N);
for (int i = 0; i < N; i++) mpm[XmD[i].second] = i;
i64 S = c;
i64 s = 0, e = 1e15 + 1e14;
while (s < e) {
vector<i64> bounds = {NINF, PINF, NINF, PINF};
i64 m = (s + e) >> 1;
i64 mms = m - S;
i64 curMax, curMin;
int ptr = 0;
int ptrm = 0;
vector<bool> vst(N);
for (int i = 0; i < N; i++) {
while (ptr < N && XpD[ptr].first <= m + XmD[i].first)
vst[mpm[XpD[ptr].second]] = true, ++ptr;
while (ptrm < N && vst[ptrm]) ++ptrm;
if (ptr == N || ptrm == N) break;
i64 xmd = X[XmD[i].second] - D[XmD[i].second];
i64 xpd = X[XmD[i].second] + D[XmD[i].second];
int sptr = ptr;
if (XpD[sptr].second == XmD[i].second) sptr++;
if (XmD[i].second != XpD[N - 1].second)
curMax = XpD[N - 1].first;
else if (sptr != N - 1)
curMax = XpD[N - 2].first;
else
continue;
if (ptrm != i)
curMin = XmD[ptrm].first;
else {
int tmp = ptrm + 1;
while (tmp < N && vst[tmp]) ++tmp;
if (tmp == N) continue;
curMin = XmD[tmp].first;
}
Helper::setmax(bounds[0], -mms - xmd + curMax);
Helper::setmin(bounds[1], mms - xpd + curMin);
Helper::setmax(bounds[2], -mms + xpd + curMax);
Helper::setmin(bounds[3], mms + xmd + curMin);
if (bounds[0] > bounds[1] || bounds[2] > bounds[3]) break;
}
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;
}
