#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<58;
long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
vector<ll> p(n), lef(n+1, -inf), rig(n+1, -inf), tmp(n), vl(n+1, -inf), vr(n+1, -inf);
vector<pii> ls(n), rs(n), a(n);
for (int i = 1;i < n;i++) p[i] = p[i-1] + L[i-1];
for (int i = 0;i < n;i++) {
a[i] = {p[i] + D[i], i};
vl[i] = D[i] - p[i];
vr[i] = D[i] + p[i];
}
sort(a.begin(), a.end());
for (int i = 0;i < n;i++) {
int id = a[i].ss;
lef[i] = D[id] - p[id];
rig[i] = D[id] + p[id];
ls[i] = {id, n};
rs[i] = {id, n};
}
for (int i = n - 2;i >= 0;i--) {
int se = ls[i].ff;
if (vl[ls[i+1].ff] < vl[se]) {
se = ls[i+1].ff;
} else {
ls[i].ff = ls[i+1].ff;
}
if (vl[se] > vl[ls[i+1].ss]) ls[i].ss = se;
else ls[i].ss = ls[i+1].ss;
se = rs[i].ff;
if (vr[rs[i+1].ff] < vr[se]) {
se = rs[i+1].ff;
} else {
rs[i].ff = rs[i+1].ff;
}
if (vr[se] > vr[rs[i+1].ss]) rs[i].ss = se;
else rs[i].ss = rs[i+1].ss;
}
rig.pop_back(), lef.pop_back();
pary(lef.begin(), lef.end());
pary(rig.begin(), rig.end());
for (int i = 0;i < n;i++) debug("lef", i, ls[i].ff, ls[i].ss);
ll low = 0, up = inf;
while (low < up - 1) {
ll M = (low + up) / 2;
ll lb = -inf, rb = inf, db = -inf, ub = inf;
debug("M", M);
for (int i = 0;i < n-1;i++) {
int ind = upper_bound(rig.begin(), rig.end(), M - (D[i] - p[i])) - rig.begin();
//[ind, n);
debug(i, ind, ls[ind].ff, ls[ind].ss);
if (ind == n) continue;
ll len = M - D[i] - C;
ll l = (rs[ind].ff != i ? vr[rs[ind].ff] : vr[rs[ind].ss]) - len,
r = -(ls[ind].ff != i ? vl[ls[ind].ff] : vl[ls[ind].ss]) + len;
debug("l", l, "r", r);
//square with two points at [l, r]
lb = max(lb, p[i] - r);
rb = min(rb, p[i] - l);
db = max(db, p[i] + l);
ub = min(ub, p[i] + r);
}
debug(M, lb, rb, db, ub);
if (rb < lb || ub < db) low = M;
else {
bool good = 0;
for (int i = 0;i < n;i++) {
ll mi = max(db - p[i], -rb + p[i]);
ll ma = min(ub - p[i], -lb + p[i]);
int ind = lower_bound(p.begin(), p.end(), mi) - p.begin();
if (ind != n && p[ind] <= ma) {
good = 1;
break;
}
}
if (good) up = M;
else low = M;
}
}
return up;
}
/*
2 4
10
28 37
2 1
3
7 2
*/
