#include "nile.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=1e9;
vector<ll>calculate_costs(vector<int>W,vector<int>A,vector<int>B,vector<int>E){
int n=W.size(),q=E.size();
vector<int>ordW(n),ordE(q),w(n),c(n),len(n);
iota(ordW.begin(),ordW.end(),0),iota(ordE.begin(),ordE.end(),0);
sort(ordW.begin(),ordW.end(),[&](int i,int j){return W[i]<W[j];});
sort(ordE.begin(),ordE.end(),[&](int i,int j){return E[i]<E[j];});
for(int i=0;i<n;i++)w[i]=W[ordW[i]],c[i]=A[ordW[i]]-B[ordW[i]];
vector<array<int,3>>e;
vector<array<int,3>>mnc(n);
for(int i=0;i<n;i++)i+1<n?e.push_back({w[i+1]-w[i],i,1}),0:0,i+2<n?e.push_back({w[i+2]-w[i],i,0}),0:0;
sort(e.rbegin(),e.rend());
set<int>s;
ll sum=0;
for(int i=0;i<n;i++)s.insert(i),len[i]=1,mnc[i]={INF,INF,INF},mnc[i][i&1]=c[i],sum+=c[i];
auto cost=[&](int i){return mnc[i][mnc[i][i&1]<mnc[i][2]?i&1:2]*(len[i]&1);};
auto mrg=[&](int i){
int j=*prev(s.upper_bound(i)),k=i+1;
sum-=cost(j),sum-=cost(k),s.erase(k),len[j]+=len[k];
for(int p=0;p<3;p++)mnc[j][p]=min(mnc[j][p],mnc[k][p]);
sum+=cost(j);
};
auto upd=[&](int i){
int j=*prev(s.upper_bound(i));
sum-=cost(j),mnc[j][2]=min(mnc[j][2],c[i]),sum+=cost(j);
};
vector<ll>R(q,accumulate(B.begin(),B.end(),0ll));
for(int i=0;i<q;i++){
while(e.size()&&e.back()[0]<=E[ordE[i]]){
auto[_,v,x]=e.back();
e.pop_back(),x?mrg(v):upd(v+1);
}
R[ordE[i]]+=sum;
}
return R;
}
