#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 10000000000000000LL
int n, c;
vector<long long> xpd, xmd;
vector<long long> x;
int sp[1000005][20];
int lg[1000005];
int get(int l, int r){
int sz = lg[r - l + 1];
int q2 = sp[r][sz];
int q1 = sp[l + (1 << sz) - 1][sz];
if(xmd[q1] < xmd[q2]) return q1;
return q2;
}
bool pos(long long len){
long long bpmx, bpmn, bmmx, bmmn, pmx, mmn, f = len - c;
bpmx = bmmx = mmn = inf;
bpmn = bmmn = pmx = -inf;
int mid = 0;
int itm = 0, itp = 0, t = 0, r;
for(itp = 1; itp < n; itp++){
if(xpd[itp] - xmd[mid] > len) break;
if(xmd[itp] <= xmd[mid]) mid = itp;
}
t = mid;
for(;itp < n; itp++){
if(t != itp - 1){
r = get(t + 1, itp - 1);
while(xpd[itp] - xmd[r] > len){
t = r;
if(t == itp - 1) break;
r = get(t + 1, itp - 1);
}
}
while(itm <= t){
mmn = min(mmn, xmd[itm]);
pmx = max(pmx, xpd[itm]);
itm++;
}
bpmx = min(bpmx, f + mmn + xmd[itp]);
bpmn = max(bpmn, -f + pmx + xpd[itp]);
bmmx = min(bmmx, f - pmx + xmd[itp]);
bmmn = max(bmmn, -f - mmn + xpd[itp]);
if(bmmx < bmmn || bpmx < bpmn) return 0;
}
int i, imn = 0, imx = 0;
for(i = 0; i < n; i++){
while(imx < n && x[i] - x[imx] > bmmx) imx++;
while(imn < n && x[i] - x[imn] >= bmmn) imn++;
if(imn > imx){
if(x[i] + x[imn - 1] <= bpmx && x[i] + x[imn - 1] >= bpmx) return 1;
if(x[i] + x[imx] <= bpmx && x[i] + x[imx] >= bpmx) return 1;
}
}
imn = n - 1;
imx = n - 1;
for(i = 0; i < n; i++){
while(imx >= 0 && x[i] + x[imx] > bpmx) imx--;
while(imn >= 0 && x[i] + x[imn] >= bpmn) imn--;
if(i > imx) return 0;
if(imn < imx){
if(x[imx] - x[i] <= bmmx && x[imx] - x[i] >= bmmn) return 1;
if(x[imn + 1] - x[i] <= bmmx && x[imn + 1] - x[i] >= bmmn) return 1;
}
}
return 0;
}
long long find_shortcut(int n, vector<int> le, vector<int> d, int c){
long long m, l = 0, r;
::c = c;
::n = n;
x.push_back(0);
for(auto& t : le){
x.push_back(x.back() + t);
}
for(int i = 0; i < n; i++){
xpd.push_back(x[i] + d[i]);
xmd.push_back(x[i] - d[i]);
}
r = x[n - 1] + 2000000000;
for(int i = 0; i < n; i++){
sp[i][0] = i;
for(int j = 1; j < 20; j++){
if((1 << j) > i) break;
int q1, q2;
q1 = sp[i][j - 1];
q2 = sp[i - (1 << (j - 1))][j - 1];
if(xmd[q1] < xmd[q2])
sp[i][j] = q1;
else sp[i][j] = q2;
}
}
for(int i = 2; i < n; i++){
lg[i] = lg[i >> 1] + 1;
}
while(l != r){
m = (l + r) >> 1;
if(pos(m)) r = m;
else l = m + 1;
}
return l;
}
