#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
#define int ll
const int N = 100005;
const ll inf = 1e15;
struct obiect {
ll w, a, b;
const bool operator < (const obiect &oth) {
return w < oth.w;
}
};
struct SegMin {
ll aint[4 * N];
int n;
void build(int pos, int st, int dr, vector<ll> &val) {
if (st == dr) {
aint[pos] = val[st];
return;
}
int mid = (st + dr) / 2;
build(2 * pos, st, mid, val);
build(2 * pos + 1, mid + 1, dr, val);
aint[pos] = min(aint[2 * pos], aint[2 * pos + 1]);
}
void init(int _n, vector<ll> val) {
n = _n;
build(1, 1, n, val);
}
void _update(int pos, int st, int dr, int loc, ll val) {
if (st == dr) {
aint[pos] = val;
return;
}
int mid = (st + dr) / 2;
if (loc <= mid) {
_update(2 * pos, st, mid, loc, val);
} else {
_update(2 * pos + 1, mid + 1, dr, loc, val);
}
aint[pos] = min(aint[2 * pos], aint[2 * pos + 1]);
}
ll _query(int pos, int st, int dr, int l, int r) {
if (l <= st && dr <= r) {
return aint[pos];
}
int mid = (st + dr) / 2;
if (r <= mid) {
return _query(2 * pos, st, mid, l, r);
} else if (mid < l) {
return _query(2 * pos + 1, mid + 1, dr, l, r);
} else {
return min(_query(2 * pos, st, mid, l, r), _query(2 * pos + 1, mid + 1, dr, l, r));
}
}
ll query(int l, int r) {
if (l > r) {
return inf;
}
return _query(1, 1, n, l, r);
}
void update(int pos, ll val) { _update(1, 1, n, pos, val); }
} par, impar, no2par, no2impar;
ll sp[N];
void update (int pos) {
//cout << "Update: " << pos << '\n';
if (pos % 2 == 0) {
par.update(pos / 2 + 1, inf);
} else {
impar.update(pos / 2 + 1, inf);
}
}
ll calc(int l, int r) {
//cout << "Calc: " << l << " " << r << '\n';
ll sum = sp[r + 1] - sp[l];
//cout << "SUM: " << sum << '\n';
if ((r - l + 1) % 2 == 0) {
//cout << "SumPar: " << sum << '\n';
return sum;
}
if (l % 2 == 1) {
sum = sum + min(no2impar.query(l / 2 + 1, r / 2 + 1), par.query((l + 1) / 2 + 1, (r - 1) / 2 + 1));
} else if (r != 0) {
sum = sum + min(no2par.query(l / 2 + 1, r / 2 + 1), impar.query((l + 1) / 2 + 1, (r - 1) / 2 + 1));
} else {
sum = sum + no2par.query(1, 1);
}
//cout << "SumImpar: " << sum << '\n';
return sum;
}
std::vector<long long> calculate_costs(std::vector<signed> w, std::vector<signed> a, std::vector<signed> b, std::vector<signed> e) {
ll n = w.size(), q = e.size();
vector<obiect> v;
for (int i = 0; i < n; i ++) {
v.push_back({w[i], a[i], b[i]});
}
vector<pair<ll, ll>> vp;
for (int i = 0; i < q; i ++) {
vp.push_back({e[i], i});
}
sort(v.begin(), v.end());
sort(vp.begin(), vp.end());
reverse(vp.begin(), vp.end());
//for (auto i : v) {
//cout << i.w << " " << i.a << " " << i.b << '\n';
//}
vector<ll> initPar(1, 0);
for (int i = 0; i < n; i += 2) {
initPar.push_back(v[i].a - v[i].b);
}
par.init(initPar.size() - 1, initPar);
no2par.init(initPar.size() - 1, initPar);
vector<ll> initImpar(1, 0);
for (int i = 1; i < n; i += 2) {
initImpar.push_back(v[i].a - v[i].b);
}
impar.init(initImpar.size() - 1, initImpar);
no2impar.init(initImpar.size() - 1, initImpar);
//cout << "SP: ";
for (int i = 1; i <= n; i ++) {
sp[i] = sp[i - 1] + v[i - 1].b;
//cout << sp[i] << " ";
}
//cout << '\n';
set<ll> brk;
brk.insert(-1);
brk.insert(n - 1);
update(0);
update(n - 1);
ll ans = calc(0, n - 1);
vector<pair<ll, ll>> diff, diff2;
for (int i = 0; i < n - 1; i ++) {
diff.push_back({v[i + 1].w - v[i].w, i});
if (i) {
diff2.push_back({v[i + 1].w - v[i - 1].w, i});
}
}
int pdiff = 0, pdiff2 = 0;
sort(diff.begin(), diff.end());
sort(diff2.begin(), diff2.end());
reverse(diff.begin(), diff.end());
reverse(diff2.begin(), diff2.end());
vector<ll> rasp(q);
//for (auto i : diff) {
//cout << i.first << " " << i.second << '\n';
//}
for (auto i : vp) {
while (pdiff < n - 1 && diff[pdiff].first > i.first) {
auto it = brk.lower_bound(diff[pdiff].second);
auto high = *it;
auto low = *(--it);
//cout << "Break: " << diff[pdiff].second << '\n';
ans -= calc(low + 1, high);
ans += calc(low + 1, diff[pdiff].second);
ans += calc(diff[pdiff].second + 1, high);
brk.insert(diff[pdiff].second);
pdiff ++;
}
while (pdiff2 < n - 2 && diff2[pdiff2].first > i.first) {
auto it = brk.lower_bound(diff2[pdiff2].second);
auto high = *it;
auto low = *(--it);
ans -= calc(low + 1, high);
update(diff2[pdiff2].second);
ans += calc(low + 1, high);
pdiff2 ++;
}
//cout << "Answer: " << ans << '\n';
rasp[i.second] = ans;
}
return rasp;
}
