#include <bits/stdc++.h>
#include "shortcut.h"
#define f first
#define s second
#define ent '\n'
typedef long long ll;
using namespace std;
const int maxn = 1e6 + 12;
int L[maxn], prmn[maxn];
int R[maxn], sfmx[maxn];
bool add[maxn];
int posq[maxn];
int p[maxn], q[maxn], l[maxn];
ll mx[maxn], mn[maxn];
ll pref[maxn], d[maxn];
int n, c;
void upd(int i, ll x){
for(; i <= n; i |= (i + 1)){
mx[i] = max(mx[i], x);
}
}
ll get(int i){
ll Mx = -1e18;
for(; i > 0; i = (i & (i + 1)) - 1){
Mx = max(Mx, mx[i]);
}
return Mx;
}
bool check2(ll D){
ll x1 = 0, x2 = 1e18, y1 = 0, y2 = 1e18;
for(int i=0;i<=n;i++){
mx[i] = -1e18;
}
for(int i=1, j=0;i<=n;i++){
while(j < n && pref[p[j+1]] - d[p[j+1]] < pref[q[i]] + d[q[i]] - D){
j++;
upd(p[j], pref[p[j]] + d[p[j]]);
add[p[j]] = 1;
}
ll mx = get(q[i]-1);
ll x = p[L[q[i]]], mn = pref[x] - d[x];
if(mn >= 1e17 || mn >= pref[q[i]] + d[q[i]] - D) continue;
ll ly = mx + d[q[i]] + c - D, ry = mn + D - d[q[i]] - c;
x2 = min(x2, pref[q[i]] + ry);
y1 = max(y1, pref[q[i]] - ry), y2 = min(y2, pref[q[i]] - ly);
}
for(int i=n;i;i--){
ll x = q[R[p[i]]], mx = pref[x] + d[x];
if(mx > pref[p[i]] - d[p[i]] + D && x > p[i]){
x1 = max(x1, mx + pref[p[i]] + d[p[i]] + c - D);
}
}
if(x1 > x2 || y1 > y2) return 0;
for(int i=n, j = 1;i;i--){
while(j <= n && x1 - pref[i] > pref[j]){
j++;
}
l[i] = j;
}
for(int i=1, j=1;i<=n;i++){
while(j <= n && pref[i] - y2 > pref[j]){
j++;
}
l[i] = max(l[i], j);
if(l[i] < i && y1 <= pref[i] - pref[l[i]] && pref[i] - pref[l[i]] <= y2 && x1 <= pref[i] + pref[l[i]] && pref[i] + pref[l[i]] <= x2){
return 1;
}
}
return 0;
}
bool check(ll D){
if(n <= 3e5){
return check2(D);
}
ll x1 = 0, x2 = 1e18, y1 = 0, y2 = 1e18;
for(int i=1;i<=n;i++){
ll x = q[R[i]], mx = pref[x] + d[x];
if(mx > pref[i] - d[i] + D && x != i){
x1 = max(x1, mx + pref[i] + d[i] + c - D);
y2 = min(y2, pref[x] - pref[i] - d[i] - d[x] - c + D);
}
x = p[L[i]];
ll mn = pref[x] - d[x];
if(mn >= 1e17 || mn >= pref[i] + d[i] - D) continue;
ll ry = mn + D - d[i] - c;
x2 = min(x2, pref[i] + ry);
y1 = max(y1, pref[i] - ry);
}
int x = 0, y = 0;
for(int t=1, j = 0;t<=n;t++){
int i = q[t];
while(pref[p[j+1]] - d[p[j+1]] < pref[i] + d[i] - D){
j++;
if(pref[p[j]] + d[p[j]] > pref[x] + d[x] || x == 0){
y = x;
x = p[j];
}
else if(pref[p[j]] + d[p[j]] > pref[y] + d[y] || y == 0){
y = p[j];
}
}
if(x != i){
if(x != 0) {
y2 = min(y2, pref[i] - pref[x] - d[x] - d[i] - c + D);
x1 = max(x1, pref[i] + pref[x] + d[x] + d[i] + c - D);
}
}
else{
if(y != 0) {
y2 = min(y2, pref[i] - pref[y] - d[y] - d[i] - c + D);
x1 = max(x1, pref[i] + pref[y] + d[y] + d[i] + c - D);
}
}
}
if(x1 > x2 || y1 > y2) return 0;
for(int i=n, j = 1;i;i--){
while(j <= n && x1 - pref[i] > pref[j]){
j++;
}
l[i] = j;
}
for(int i=1, j=1;i<=n;i++){
while(j <= n && pref[i] - y2 > pref[j]){
j++;
}
l[i] = max(l[i], j);
if(l[i] < i && y1 <= pref[i] - pref[l[i]] && pref[i] - pref[l[i]] <= y2 && x1 <= pref[i] + pref[l[i]] && pref[i] + pref[l[i]] <= x2){
return 1;
}
}
return 0;
}
ll find_shortcut(int N, vector<int> l, vector<int> D, int C){
n = N, c = C;
for(int i=2;i<=n;i++){
pref[i] = pref[i-1] + l[i-2];
}
for(int i=1;i<=n;i++){
d[i] = D[i-1];
p[i] = i;
q[i] = i;
}
sort(p+1, p+n+1, [](int i, int j){
return pref[i] - d[i] < pref[j] - d[j];
});
sort(q+1, q+n+1, [](int i, int j){
return pref[i] + d[i] < pref[j] + d[j];
});
prmn[0] = 1e9;
for(int i=1;i<=n;i++){
prmn[i] = min(prmn[i-1], p[i]);
}
sfmx[n+1] = -1e9;
for(int i=n;i;i--){
sfmx[i] = max(sfmx[i+1], q[i]);
}
p[n+1] = n + 1;
pref[n+1] = 1e18;
pref[0] = -1e18;
for(int i=1;i<=n;i++){
L[i] = n + 1, R[i] = 0;
for(int l=1, r=n;l<=r;){
int mid = l + r >> 1;
if(prmn[mid] < i){
L[i] = mid;
r = mid - 1;
}
else l = mid + 1;
}
for(int l=1, r=n;l<=r;){
int mid = l + r >> 1;
if(sfmx[mid] > i){
R[i] = mid;
l = mid + 1;
}
else r = mid - 1;
}
}
ll ans = 0;
for(ll l = 0, r = 1e15 + 2e9; l <= r;){
ll mid = l + r >> 1;
bool c = 0;
if(check(mid)){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
return ans;
}
