#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define X first
#define Y second
int n, c;
ll d[1000007], x[1000007];
vector<pll> VP, VM;
//x[j] <= min(maxs - x[i], maxd + x[i])
//x[j] >= max(mins - x[i], mind + x[i])
bool find_pair(ll mins, ll maxs, ll mind, ll maxd) {
for(int i = 1 ; i < n ; i++) {
ll minv = max(mins - x[i], mind + x[i]);
ll maxv = min(maxs - x[i], maxd + x[i]);
auto it = lower_bound(x + i + 1, x + n + 1, minv);
if(it != x + n + 1 && (*it) <= maxv)
return true;
}
return false;
}
bool check(ll k) {
ll mins = 0, maxs = 1e18, mind = 0, maxd = 1e18;
ll minis = 1e18, maxis = 0;
int ii = 0;
for(int jj = 0 ; jj < n ; jj++) {
int j = VP[jj].Y;
while(ii < n && VM[ii].X + k < VP[jj].X) {
int i = VM[ii].Y;
minis = min(minis, x[i] + d[i]);
maxis = max(maxis, x[i] + d[i]);
ii++;
}
if(ii && 2 * d[j] <= k) {
mins = max(mins, VP[jj].X + maxis - k + c);
maxs = min(maxs, k - c + (x[j] - d[j]) + VM[0].X);
mind = max(mind, VP[jj].X - VM[0].X - k + c);
maxd = min(maxd, k - c + (x[j] - d[j]) - maxis);
}
//~ cout << k << " " <<minis << " " << maxis << " " << mins << " " << maxs << " " << mind << " " << maxd << endl;
}
for(int j = 1 ; j <= n ; j++) {
if(2 * d[j] > k) {
for(int i = 1 ; i < j ; i++) {
if(x[i] - d[i] + k < x[j] + d[j]) {
mins = max(mins, x[j] + d[j] + x[i] + d[i] - k + c);
maxs = min(maxs, k - c + (x[j] - d[j]) + x[i] - d[i]);
mind = max(mind, x[j] + d[j] - (x[i] - d[i]) - k + c);
maxd = min(maxd, k - c + (x[j] - d[j]) - (x[i] + d[i]));
}
}
}
}
//~ cout << k << " " << mins << " " << maxs << " " << mind << " " << maxd << endl;
return find_pair(mins, maxs, mind, maxd);
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> dd, int c) {
d[1] = dd[0];
::n = n;
::c = c;
for(int i = 1 ; i < n ; i++) {
x[i + 1] = x[i] + l[i - 1];
d[i + 1] = dd[i];
}
int max1 = 0, max2 = 0;
for(int i = 1 ; i <= n ; i++) {
VP.emplace_back(x[i] + d[i], i);
VM.emplace_back(x[i] - d[i], i);
if(d[i] >= max1) {
max2 = max1;
max1 = d[i];
} else if(d[i] > max2)
max2 = d[i];
}
sort(VP.begin(), VP.end());
sort(VM.begin(), VM.end());
ll a = max1 + max2, b = 1e18, mid;
while(a < b) {
mid = (a + b) / 2;
if(check(mid))
b = mid;
else
a = mid + 1;
}
return a;
}
