#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;
bool find_pair(ll mins, ll maxs, ll mind, ll maxd) {
for(int i = 1 ; i < n ; i++)
for(int j = i + 1 ; j <= n ; j++)
if(mins <= x[i] + x[j] && x[i] + x[j] <= maxs && x[j] - x[i] >= mind && x[j] - x[i] <= maxd)
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) {
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 << " " << 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;
}
