#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int Q = (int)E.size(), n = (int)A.size();
long long sum = 0, diff, diffe = 0;
std::vector<long long> R(Q, 0);
vector <pair<int, int>> F;
for (int i = 0; i < Q; i++){
F.push_back({E[i], i});
}
vector <long long> diffs;
sort(F.begin(), F.end());
vector <pair<int, long long>> C;
for (int i = 0; i < A.size(); i++){
C.push_back({W[i], A[i] - B[i]});
diff = B[i];
sum += diff;
}
sort(C.begin(), C.end());
vector <pair<long long, pair<int, int>>> costs;
for (int i = 0; i < n - 1; i++){
costs.push_back({C[i+1].first - C[i].first, {i, i + 1}});
if (i < n - 2) costs.push_back({C[i+2].first - C[i].first, {i, i + 2}});
}
sort(costs.begin(), costs.end());
vector <pair<int, int>> segments;
vector<long long> mino, mine, mins;
for (int i = 0; i < n; i++){
segments.push_back({i, i});
diffs.push_back(C[i].second);
diffe += C[i].second;
if (i % 2 == 0){
mine.push_back(C[i].second);
mino.push_back(INT_MAX);
mins.push_back(INT_MAX);
}
else{
mino.push_back(C[i].second);
mine.push_back(INT_MAX);
mins.push_back(INT_MAX);
}
}
int cur = 0;
for (int i = 0; i < Q; i++){
int q = F[i].first, s = F[i].second;
while (cur != costs.size() && costs[cur].first <= q){
int a = costs[cur].second.first;
int b = costs[cur].second.second;
if (b - a == 1){
int start = 0, ends = segments.size() - 2;
while (segments[start].second != a){
int k = (start + ends + 1) / 2;
if (segments[k].second <= a){
start = k;
}
else ends = k - 1;
}
diffe -= diffs[start];
diffe -= diffs[start+1];
segments.insert(segments.begin() + start, {segments[start].first, segments[start+1].second});
segments.erase(segments.begin() + start + 1);
segments.erase(segments.begin() + start + 1);
diffs.erase(diffs.begin() + start);
diffs.erase(diffs.begin() + start);
mins.insert(mins.begin() + start, min(mins[start], mins[start+1]));
mins.erase(mins.begin() + start + 1);
mins.erase(mins.begin() + start + 1);
mino.insert(mino.begin() + start, min(mino[start], mino[start+1]));
mino.erase(mino.begin() + start + 1);
mino.erase(mino.begin() + start + 1);
mine.insert(mine.begin() + start, min(mine[start], mine[start+1]));
mine.erase(mine.begin() + start + 1);
mine.erase(mine.begin() + start + 1);
if ((segments[start].second + 1 - segments[start].first) % 2 == 0) diffs.insert(diffs.begin() + start, 0);
else{
long long g;
if (segments[start].first % 2 == 0){
g = mine[start];
}
else g = mino[start];
g = min(g, mins[start]);
diffs.insert(diffs.begin() + start, g);
diffe += g;
}
}
else{
int start = 0, ends = segments.size() - 1;
while (start != ends){
int k = (start + ends + 1) / 2;
if (segments[k].first <= a){
start = k;
}
else ends = k - 1;
}
mins[start] = min(mins[start], C[a+1].second);
diffe -= diffs[start];
diffs[start] = min(diffs[start], mins[start]);
diffe += diffs[start];
}
cur++;
}
R[s] = sum + diffe;
}
return R;
}
