// M
#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const int N = 300005;
int n, cost, P[N], Rev[N], Target[N];
ll X[N], L[N], D[N];
ll F[2][N];
inline void Add(int w, int i, ll val)
{
for (; i < N; i += i & - i)
F[w][i] = max(F[w][i], val);
}
inline ll GetMax(int w, int i)
{
ll Mx = -1e18;
for (; i; i -= i & - i)
Mx = max(Mx, F[w][i]);
return Mx;
}
inline bool Solve(ll md)
{
memset(F, -63, sizeof(F));
for (int i = 1; i <= n; i ++)
{
int le = 0, ri = n + 1, mid;
while (ri - le > 1)
{
mid = (le + ri) >> 1;
if (D[P[mid]] - X[P[mid]] + D[i] + X[i] > md)
le = mid;
else
ri = mid;
}
Target[i] = le;
}
ll le_sm = -1e18, ri_sm = 1e18;
ll le_mn = -1e18, ri_mn = 1e18;
for (int j = 1; j <= n; j ++)
{
// Optimizing all the nonsense from below :
// Let's break it down :
// 1. X[i]-a + X[j]-b <= value ==> a + b >= (X[i] + D[i]) + (X[j] + D[j]) - (md - cost)
// 2. X[i]-a + b-X[j] <= value ==> b - a <= (md - cost) + (X[j] - D[j]) - (X[i] + D[i])
// 3. a-X[i] + X[j]-b <= value ==> b - a >= (X[j] + D[j]) - (X[i] - D[i]) - (md - cost)
// 4. a-X[i] + b-X[j] <= value ==> b + a <= (md - cost) + (X[i] - D[i]) + (X[j] - D[j])
le_sm = max(le_sm, X[j] + D[j] - (md - cost) + GetMax(0, Target[j]));
ri_sm = min(ri_sm, (md - cost) + (X[j] - D[j]) - GetMax(1, Target[j]));
le_mn = max(le_mn, X[j] + D[j] - (md - cost) + GetMax(1, Target[j]));
ri_mn = min(ri_mn, (md - cost) + (X[j] - D[j]) - GetMax(0, Target[j]));
Add(0, Rev[j], X[j] + D[j]),
Add(1, Rev[j], D[j] - X[j]);
/* This is gibberish now.
// Requiring a bridge of form (a, b) where
// D[i] + D[j] + |X[i]-a| + |X[j]-b| + cost <= md
// |X[i]-a| + |X[j]-b| <= md - cost - D[i] - D[j]
ll value = md - cost - D[i] - D[j];
// Let's break it down :
// 1. X[i]-a + X[j]-b <= value ==> a + b >= X[i] + X[j] - value
// 2. X[i]-a + b-X[j] <= value ==> b - a <= value + X[j] - X[i]
// 3. a-X[i] + X[j]-b <= value ==> b - a >= X[j] - X[i] - value
// 4. a-X[i] + b-X[j] <= value ==> b + a <= value + X[i] + X[j]
le_sm = max(le_sm, X[i] + X[j] - value); // 1.
ri_sm = min(ri_sm, value + X[i] + X[j]); // 4.
le_mn = max(le_mn, X[j] - X[i] - value); // 3.
ri_mn = min(ri_mn, value + X[j] - X[i]); // 2.
*/
}
for (int j = 1; j <= n; j ++)
{
// le_sm <= X[j] + X[i] ==> le_sm - X[j] <= X[i]
// ri_sm >= X[j] + X[i] ==> ri_sm - X[j] >= X[i]
// le_mn <= X[j] - X[i] ==> X[j] - le_mn >= X[i]
// ri_mn >= X[j] - X[i] ==> X[j] - ri_mn <= X[i]
ll le_val = max(le_sm - X[j], X[j] - ri_mn);
ll ri_val = min(ri_sm - X[j], X[j] - le_mn);
int i = lower_bound(X + 1, X + j + 1, le_val) - X;
if (i <= j && X[i] >= le_val && X[i] <= ri_val)
return 1;
}
/*
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
if (X[i] + X[j] >= le_sm && X[i] + X[j] <= ri_sm && X[j] - X[i] >= le_mn && X[j] - X[i] <= ri_mn)
return 1;*/
return 0;
}
long long find_shortcut(int _n, vector < int > _L, vector < int > _D, int _cost)
{
n = _n;
cost = _cost;
for (int i = 1; i < n; i ++)
L[i] = _L[i - 1];
for (int i = 1; i <= n; i ++)
D[i] = _D[i - 1];
for (int i = 2; i <= n; i ++)
X[i] = X[i - 1] + L[i - 1];
for (int i = 1; i <= n; i ++)
P[i] = i;
sort(P + 1, P + n + 1, [&](int i, int j){return make_pair(D[i] - X[i], i) > make_pair(D[j] - X[j], j);});
for (int i = 1; i <= n; i ++)
Rev[P[i]] = i;
ll le = 0, ri = 7e15, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Solve(md))
ri = md;
else
le = md;
}
return ri;
}
