#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e6+100;
const ll INF = 1e18;
ll x[MAXN];
ll d[MAXN];
ll c;
ll n;
bool check(ll k){
ll suml,sumr,difl,difr;
suml = difl = -INF;
sumr = difr = +INF;
ll msum,mdif;
msum = -INF,mdif=INF;
deque <ll> dq;
for (ll i = 0;i < n;i ++){
if (i && x[i] + d[i] - mdif > k){
// if (k==50)cout<<"SUS"<<endl;
while (sz(dq) && -(x[dq.front()] - d[dq.front()]) + x[i] + d[i] > k){
msum = max(msum,x[dq.front()] + d[dq.front()]);
dq.pop_front();
}
suml = max(suml,x[i]+d[i]+msum+c-k);
sumr = min(sumr,x[i]-d[i]+mdif+k-c);
difl = max(difl,x[i]+d[i]-mdif+c-k);
difr = min(difr,x[i]-d[i]-msum+k-c);
}
mdif = min(mdif,x[i]-d[i]);
while (sz(dq) && x[dq.back()] - d[dq.back()] >= x[i] - d[i])dq.pop_back();
dq.push_back(i);
}
// if (k==50)cout<<suml<<' '<<sumr<<' '<<difl<<' '<<difr<<endl;
ll Ls,Rs,Ld,Rd;
Ls = n - 1,Rs = n - 1;
Ld = 0,Rd = 0;
for (ll i = 0;i < n;i ++){
while (Ls && x[Ls] + x[i] >= suml)Ls--;
while (Rs && x[Rs] + x[i] > sumr)Rs--;
//Ls + 1 -> Rs
while (Ld < n && x[Ld] - x[i] < difl)Ld++;
while (Rd < n && x[Rd] - x[i] <= difr)Rd++;
//Ld -> Rd - 1
//z > y
if (max({Ld,Ls+1,i+1}) <= min({Rs,Rd-1}))return 1;
}
return 0;
}
long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int C)
{
n=N;
c = C;
for (ll i = 0;i < n;i ++)d[i] = D[i];
x[0] = 0;
for (ll i = 1;i < n;i ++)x[i] = x[i-1] + L[i-1];
ll l = 0;
ll r = 1e17;
while (l <= r){
ll mid = (l + r) >> 1;
if (check(mid)){
r = mid - 1;
}
else l = mid + 1;
}
return l;
}
