#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 1;
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
vector<int> w = W, a = A, b = B, e = E;
int n = w.size(), q = e.size();
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int l, int r)
{
return w[l] < w[r];
});
vector<int> lg(n + 1);
lg[1] = 0;
for(int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
vector spt(n, vector<int>(21));
for(int i = 0; i < n; i++)
spt[i][0] = ord[i];
for(int j = 1; j < 21; j++)
for(int i = 0; i + (1 << (j - 1)) < n; i++)
{
int x = spt[i][j - 1], y = spt[i + (1 << (j - 1))][j - 1];
if(a[x] - b[x] < a[y] - b[y])
spt[i][j] = x;
else
spt[i][j] = y;
// spt[i + (1 << (j - 1))][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
}
auto get_min = [&](int l, int r) -> int
{
int j = lg[r - l + 1];
int x = spt[l][j], y = spt[r - (1 << j) + 1][j];
if(a[x] - b[x] < a[y] - b[y])
return x;
else
return y;
// return min(spt[l][j], spt[r - (1 << j) + 1][j]);
};
map<int, vector<int>, greater<int>> mp1;
map<int, int> res;
for(int i = 1; i < n; i++)
mp1[w[ord[i]] - w[ord[i - 1]]].push_back(i);
map<int, long long> dp;
long long sum = accumulate(b.begin(), b.end(), 0ll);
if(n & 1)
{
int x = get_min(0, n - 1);
sum += a[x] - b[x];
// cout << x << ' ' << a[x] - b[x] << '\n';
}
dp[inf] = sum;
set<pair<int, int>> lst;
lst.insert({0, n - 1});
int lst_idx = inf;
for(auto [f, s]: mp1)
{
for(auto i: s)
{
auto it = prev(lst.upper_bound({i, -1}));
auto [ff, ss] = *it;
lst.erase(it);
lst.insert({ff, i - 1});
lst.insert({i, ss});
int len1 = ss - ff + 1;
int len2 = i - ff;
int len3 = ss - i + 1;
if(!(len1 & 1))
{
int x = get_min(ff, i - 1), y = get_min(i, ss);
if(len2 & 1)
dp[f] += (a[x] - b[x]) + (a[y] - b[y]);
}
else
{
int x = get_min(ff, i - 1), y = get_min(i, ss);
int z = get_min(ff, ss);
int add = -(a[z] - b[z]);
if(len2 & 1)
add += a[x] - b[x];
else
add += a[y] - b[y];
dp[f] += add;
}
}
//cout << f << '\n';
//for(auto [f, s]: lst)
//{
// cout << f << ' ' << s << '\n';
//}
dp[f] += dp[lst_idx];
lst_idx = f;
}
vector<long long> fin(q);
for(int i = 0; i < q; i++)
{
fin[i] = dp.upper_bound(e[i])->second;
}
return fin;
}
