#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int n;
vector<ll> x;
bool solve(const vector<tuple<ll, ll, ll>>& sq){
ll a = -INF, b = INF, c = INF, d = -INF;
for(auto [xc, yc, r] : sq){
a = max(a, xc-r-yc);
b = min(b, xc+r-yc);
c = min(c, xc+r+yc);
d = max(d, xc-r+yc);
}
if(a > b || c < d) return false;
int lo = 0, hi = n-1;
for(int i = 0; i < n; i++){
ll ylo = max(x[i]-b, d-x[i]);
ll yhi = min(x[i]-a, c-x[i]);
if(lo == -1) lo++;
if(hi == n) hi--;
while(lo < n-1 && x[lo] < ylo) lo++;
while(lo >= 0 && x[lo] >= ylo) lo--;
while(hi > 0 && x[hi] > yhi) hi--;
while(hi < n && x[hi] <= yhi) hi++;
if(hi-lo > 1) return true;
}
return false;
}
ll find_shortcut(int n_, vector<int> len, vector<int> d, int c) {
n = n_;
x.resize(n);
x[0] = 0;
for(int i = 0; i < n-1; i++) x[i+1] = x[i]+len[i];
ll M = x.back()+*max_element(d.begin(), d.end())*2;
ll lo = 0, hi = M;
for(ll mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
vector<tuple<ll, ll, ll>> sq;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(abs(x[i]-x[j])+d[i]+d[j] <= mid) continue;
sq.emplace_back(x[i], x[j], mid-c-d[i]-d[j]);
}
}
if(solve(sq)) hi = mid;
else lo = mid+1;
}
return lo;
}
