#include "shortcut.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <ll,ll> pi;
typedef vector <int> vec;
const ll INF = 1e18;
ll p[1000005],d[1000005];
ll di,ans;
int n;
vector <pi> lad,lsu;
int adp[1000005],sup[1000005],adrp[1000005],surp[1000005];
ll ad[1000005],su[1000005];
int t[1 << 20],bit = (1 << 19);
bool cmp_ad(int x,int y) {return ad[x] < ad[y];}
void up(int x,int wi) {
x += bit;
t[x] = wi;
x /= 2;
while(x) {
if(su[t[x]] <= su[wi]) break;
t[x] = wi;
x /= 2;
}
}
int query(ll val) {
int ret = n;
if(ad[t[1]] > val) return t[1];
for(int x = 1;x < bit*2;) {
x *= 2;
if(ad[t[x+1]] > val) {if(su[ret] > su[t[x+1]]) ret = t[x+1];}
else x++;
}
return ret;
}
bool isok(ll m) {
ll adl,adr,sul,sur;
adl = sul = -INF;
adr = sur = INF;
for(int i = 1;i < bit*2;i++) t[i] = n;
int adpo = -1;
for(int i = n-1;i >= 0;i--) {
ll v = m+p[i]-d[i];
if(adpo != -1&&ad[adpo] > v) {
int j = adpo;
ll A = p[i], B = p[j], C = m-d[i]-d[j]-di;
sur = min(sur,A-B+C);
adl = max(adl,A+B-C);
j = query(v);
B = p[j], C = m-d[i]-d[j]-di;
sul = max(sul,A-B-C);
adr = min(adr,A+B+C);
//cout << adpo << ' ' << j << '\n';
if(adl > adr||sul > sur) return 0;
}
if(adpo == -1||adrp[adpo] < adrp[i]) adpo = i;
up(adrp[i],i);
}
//cout << m << " : " << sul << ' ' << sur << ' ' << adl << ' ' << adr << '\n';
int po = 0;
for(int i = 0;i < n;i++) {
ll x = p[i],l,r;
l = max(adl-x,sul+x), r = min(adr-x,sur+x);
for(;po >= 1&&p[po-1] >= l;po--);
for(;po < n&&p[po] < l;po++);
//cout << po << '\n';
if(po < n&&p[po] <= r) return 1;
}
return 0;
}
ll find_shortcut(int N,vec len,vec dist,int gi) {
di = gi; n = N;
//for(bit = 1;bit <= n;bit *= 2);
ll lm = 0,rm = -INF;
for(int i = 0;i < n;i++) d[i] = dist[i];
for(int i = 1;i < n;i++) p[i] = p[i-1]+len[i-1];
for(int i = 0;i < n;i++) adp[i] = i;
for(int i = 0;i < n;i++) {
ad[i] = p[i]+d[i], su[i] = p[i]-d[i];
lm = max(lm,ad[i]+rm);
rm = max(rm,-su[i]);
}
ad[n] = su[n] = INF;
sort(adp,adp+n,cmp_ad);
sort(dist.rbegin(),dist.rend());
for(int i = 0;i < n;i++) adrp[adp[i]] = i;
ll l = dist[0]+dist[1], r = lm;
while(l <= r) {
//cout << l << ' ' << r <<'\n';
ll mid = (l + r) >> 1;
if(isok(mid)) r = mid-1, ans = mid;
else l = mid+1;
}
return ans;
}
