#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e6 + 10;
int n;
ll X[N];
vector<ll> W;
ll L;
vector<pii> A,B;
pii P0[N], P1[N];
pii M0[N], M1[N];
bool check(ll k){
ll mx = 0;
for(int i = 0 ; i < n; i ++ ){
if(W[i] + mx > k) return false;
mx = max(mx, W[i]);
}
ll lowplus = -(ll)1e18;
ll highplus = (ll)1e18;
ll lowminus = -(ll)1e18;
ll highminus = (ll)1e18;
/*
for(int i = 0 ; i < n; i ++ ){
for(int j = 0; j < n; j ++ ){
if(i == j) continue;
if(X[j] + W[j] - (X[i] - W[i]) <= k) continue; // no one cares
lowplus = max(lowplus, -k + X[i] + X[j] + L + W[i] + W[j]);
highplus = min(highplus, k + X[i] + X[j] - L - W[i] - W[j]);
lowminus = max(lowminus, -k + X[i] - X[j] + L + W[i] + W[j]);
highminus = min(highminus, k + X[i] - X[j] - L - W[i] - W[j]);
}
}
*/
int pi = -1;
int i,j;
ll extra;
ll Y[2];
int las;
for(int ii = 0 ; ii < n; ii ++ ){
j = A[ii].se;
while(pi + 1 < n && A[ii].fi - B[pi + 1].fi > k){
pi ++ ;
}
if(pi >= 0){
if(j == P0[pi].se) Y[0] = P1[pi].fi;
else Y[0] = P0[pi].fi;
if(j == M0[pi].se) Y[1] = M1[pi].fi;
else Y[1] = M0[pi].fi;
lowplus = max(lowplus, -k + Y[0] + X[j] + L + W[j]);
highplus = min(highplus, k + Y[1] + X[j] - L - W[j]);
lowminus = max(lowminus, -k + Y[0] - X[j] + L + W[j]);
highminus = min(highminus, k + Y[1] - X[j] - L - W[j]);
}
}
int i0 = n - 1, j0 = n - 1;
int i1 = 0, j1 = 0;
int tl, tr;
for(int i = 0 ; i < n; i ++ ){
while(i0 >= 0 && X[i] + X[i0] > highplus){
i0 -- ;
}
while(j0 > 0 && X[i] + X[j0 - 1] >= lowplus){
j0 -- ;
}
while(i1 < n && X[i] - X[i1] > highminus){
i1 ++ ;
}
while(j1 + 1 < n && X[i] - X[j1 + 1] >= lowminus){
j1 ++ ;
}
tl = i + 1;
tr = n - 1;
tl = max(tl, j0);
tr = min(tr, i0);
tl = max(tl, i1);
tr = min(tr, j1);
if(tl <= tr){
return true;
}
}
return false;
}
ll find_shortcut(int _n, vector<int> l, vector<int> _d, int _c){
n = _n;
for(int i = 1; i < n; i ++ ){
X[i] = X[i - 1] + l[i - 1];
}
for(auto x : _d)
W.push_back(x);
for(int i = 0 ; i < n; i ++ ){
A.push_back(mp(X[i] + W[i], i));
B.push_back(mp(X[i] - W[i] ,i));
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
pii PP0 = mp(-(ll)1e18, -1);
pii PP1 = mp(-(ll)1e18, -1);
pii MM0 = mp(+(ll)1e18, -1);
pii MM1 = mp(+(ll)1e18, -1);
int i;
for(int ii = 0 ; ii < n; ii ++ ){
i = B[ii].se;
if(mp(X[i] + W[i], i) > PP0){
PP1 = PP0;
PP0 = mp(X[i] + W[i], i);
}
else if(mp(X[i] + W[i], i) > PP1){
PP1 = mp(X[i] + W[i], i);
}
if(mp(X[i] - W[i], i) < MM0){
MM1 = MM0;
MM0 = mp(X[i] - W[i], i);
}
else if(mp(X[i] - W[i], i) < MM1){
MM1 = mp(X[i] - W[i], i);
}
P0[ii] = PP0;
P1[ii] = PP1;
M0[ii] = MM0;
M1[ii] = MM1;
}
L = _c;
ll li = 0;
ll ri = (ll)2e15;
ll mid;
while(li < ri){
mid = (li + ri) / 2;
if(check(mid)){
ri = mid;
}
else{
li = mid + 1;
}
}
return li;
}
