#include "nile.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int inf = 1e9 , N = 1e5 + 5;
vector<ll> sb(N);
ll sans;
int s;
vector<vector<int>> t(N * 4 , vector<int> (4 , inf));
vector<int> kur;
set<pair<int , pair<int , ll>>> st;
vector<int> mrg(vector<int> a, vector<int> b){
return {min(a[0] , b[0]) , min(a[1] , b[1]) , min(a[2] , b[2]) , min(a[3] , b[3])};
}
void update(int v , int l , int r , int j , int x , int tp){
if(r - l == 1){
if(tp == 1) t[v][l % 2] = x;
else t[v][l % 2 + 2] = x;
}
else{
int m = (l + r) / 2;
if(j < m) update(v * 2 , l , m , j , x , tp);
else update(v * 2 + 1 , m , r , j , x , tp);
t[v] = mrg(t[v * 2] , t[v * 2 + 1]);
}
}
void gett(int v , int l , int r , int l1 , int r1){
if(l <= l1 and r >= r1){
kur = mrg(kur , t[v]);
}
else{
int m = (l1 + r1) / 2;
if(!(l1 >= r || m <= l)) {
gett(v * 2 , l , r , l1 , m);
}
if(!(m >= r || r1 <= l)) {
gett(v * 2 + 1 , l , r , m , r1);
}
}
}
vector<int> get(int l , int r){
kur = {inf , inf , inf , inf};
gett(1 , l , r + 1 , 0 , s);
return kur;
}
void updt(int j , int x , int tp){
update(1 , 0 , s , j , x , tp);
}
void upd(int p){
auto to = (-- st.lower_bound({p + 1 , {-1 , -1}}));
int l = to -> fi;
int r = (to -> se).fi;
ll sm = (to -> se).se;
ll ons = sb[r];
if(l) ons -= sb[l - 1];
sans -= sm;
if((r - l + 1) % 2 == 1){
vector<int> ff = get(l , r);
//cout << l << ' ' << r << ' ' << ff[2 + ((l + 1) % 2)] << ' ';
ons += min(ff[l % 2] , ff[2 + ((l + 1) % 2)]);
}
st.erase(to);
st.insert({l , {r , ons}});
sans += (to -> se).se;
}
void unit(int p){
auto to = (st.lower_bound({p + 1 , {-1 , -1}}));
int l1 = p + 1;
int r1 = (to -> se).fi;
ll sm1 = (to -> se).se;
to --;
int l0 = to -> fi;
int r0 = p;
ll sm0 = (to -> se).se;
st.erase({l1 , {r1 , sm1}});
st.erase({l0 , {r0 , sm0}});
sans -= (sm1 + sm0);
st.insert({l0 , {r1 , 0}});
upd(l0);
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) {
int q = e.size();
int n = w.size();
s = 1;
while(s < n) s *= 2;
vector<pair<int , int>> p(n);
for(int i = 0;i < n; ++ i) p[i] = {w[i] , i};
sort(p.begin() , p.end());
vector<pair<int , pair<int , int>>> ivent;
// time , type ivent , position
for(int i = 1;i < n; ++ i){
ivent.push_back({p[i].fi - p[i - 1].fi , {1 , i - 1}});
if(i > 1) ivent.push_back({p[i].fi - p[i - 2].fi , {2 , i - 1}});
}
vector<ll> ans(q);
for(int i = 0;i < q; ++ i) ivent.push_back({e[i] , {3 , i}});
sort(ivent.begin() , ivent.end());
sb[0] = b[p[0].se];
for(int i = 0;i < n; ++ i){
sans += a[i];
st.insert({i , {i , a[p[i].se]}});
if(i) sb[i] = sb[i - 1] + b[p[i].se];
updt(i , a[p[i].se] - b[p[i].se] , 1);
}
for(auto to : ivent){
int dst = to.fi , t = to.se.fi , pos = to.se.se;
if(t == 3) ans[pos] = sans;
else if(t == 1){
unit(pos);
}
else{
updt(pos , a[p[pos].se] - b[p[pos].se] , 2);
upd(pos);
}
//cout << dst << ' ' << t << ' ' << pos << ' ' << sans << '\n';
}
return ans;
}
