#include "nile.h"
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
using st = array<ll, 4>; // S S, S D, D S, D D
#define def (st){INF, INF, INF, INF}
inline void chmin(ll &x, ll y) {x = min(x,y);}
int N, D;
vector<ll> X, W, A, B;
vector<st> tree;
vector<bool> can;
st merge(st l, st r, int tl, int tm, int tr) {
if (l == def) return r;
if (r == def) return l;
st re;
re[0] = min(l[0], l[1]) + min(r[0], r[2]);
re[1] = min(l[0], l[1]) + min(r[1], r[3]);
re[2] = min(l[2], l[3]) + min(r[0], r[2]);
re[3] = min(l[2], l[3]) + min(r[1], r[3]);
if (can[X[tm]]) {
ll dif = B[X[tm]] + B[X[tm+1]] - A[X[tm]] - A[X[tm+1]];
int lsz = tm - tl + 1, rsz = tr - tm;
if (lsz == 1 && rsz == 1) {
chmin(re[3], l[0] + r[0] + dif);
} else if (lsz == 1) {
chmin(re[2], l[0] + r[0] + dif);
chmin(re[3], l[0] + r[1] + dif);
} else if (rsz == 1) {
chmin(re[1], l[0] + r[0] + dif);
chmin(re[3], l[2] + r[0] + dif);
} else {
chmin(re[0], l[0] + r[0] + dif);
chmin(re[1], l[0] + r[1] + dif);
chmin(re[2], l[2] + r[0] + dif);
chmin(re[3], l[2] + r[1] + dif);
}
}
// cout << tl << ' ' << tr << endl;
// cout << re[0] << ' ' << re[1] << ' ' << re[2] << ' ' << re[3] << endl;
return re;
}
void update(ll v, int p, int tl = 0, int tr = N-1, int i = 1) {
if (tl == tr) {
if (v != INF) tree[i] = {v, INF, INF, INF};
return ;
}
int tm = (tl + tr) / 2;
if (p <= tm) update(v, p, tl, tm, i * 2);
else update(v, p, tm + 1, tr, i * 2 + 1);
tree[i] = merge(tree[i * 2], tree[i * 2 + 1], tl, tm, tr);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
N = W.size(); int Q = E.size();
::W.resize(N), ::A.resize(N), ::B.resize(N), can.resize(N), X.resize(N);
for(int i = 0; i < N; i++)::W[i] = W[i], ::A[i] = A[i], ::B[i] = B[i];
iota(X.begin(), X.end(), 0);
sort(X.begin(), X.end(), [&](const int a, const int b) {return W[a] < W[b];} );
vector<int> Y(Q);
iota(Y.begin(), Y.end(), 0);
sort(Y.begin(), Y.end(), [&](const int a, const int b) {return E[a] < E[b];} );
tree.resize(N*4, def);
for(int i = 0; i < N; i++) update(A[X[i]], i);
vector<pair<ll,int>> dist;
for(int i = 0; i < N-1; i++) dist.push_back({W[X[i+1]]-W[X[i]], i});
sort(dist.begin(), dist.end(), greater<>());
vector<ll> res(Q);
for(int j = 0; j < Q; j++) {
while(dist.size() && E[Y[j]] >= dist.back().first) {
// cout << "D " << dist.back().first<< ' ' << dist.back().second << endl;
can[X[dist.back().second]] = true;
update(INF, dist.back().second);
dist.pop_back();
}
res[Y[j]] = min({tree[1][0], tree[1][1], tree[1][2], tree[1][2]});
// cout << "RES " << Y[j] << ' ' << E[Y[j]] << ' ' << res[Y[j]] << endl;
}
return res;
}
