#include "nile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
const ll MAXN = 1e5+10;
const ll INF = 2e9+10;
void chmn(auto &a, auto b){ a = min(a, b); }
ll n, q, w[MAXN], a[MAXN], b[MAXN];
ll val[MAXN];
struct seg {
ll st[4*MAXN];
void bd(ll id, ll l, ll r){
st[id] = INF;
if(l==r) return;
bd(lf,l,md); bd(rg,md+1,r);
}
ll que(ll id, ll l, ll r,ll x, ll y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return INF;
return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
}
ll upd(ll id, ll l, ll r,ll x, ll p){
if(l==r && l==x) return st[id] = p;
if(r<x || x<l) return st[id];
return st[id] = min(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p));
}
} A, ODD, EV;
vector<ll> ANS;
ll ans[MAXN];
struct dsu {
ll par[MAXN];
void bd(){
for(ll i=1; i<=n; i++) par[i] = i;
}
ll f(ll x){
return (par[x]==x ? x : par[x]=f(par[x]));
}
void mer(ll x, ll y){ // x->y
x = f(x); y = f(y);
par[x] = y;
}
} LE, RI;
ll calc(ll l, ll r){
if((r-l+1)%2 == 0) return 0ll;
ll mn = min(val[l], val[r]);
if(r%2 == 1) chmn(mn, ODD.que(1,1,n,l,r));
else chmn(mn, EV.que(1,1,n,l,r));
if(l+1 <= r-1) chmn(mn, A.que(1,1,n,l+1,r-1));
return mn; // min dari tengah sm ujung
}
vector<pii> edge, two;
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> aa,
std::vector<int> B, std::vector<int> E) {
q = (ll)E.size();
n = W.size();
vector<array<ll,3>> vec;
for(ll i=0; i<n; i++)
vec.pb({W[i], aa[i], B[i]});
sort(vec.begin(), vec.end());
ll ALL = 0, mn = 0;
ODD.bd(1,1,n); EV.bd(1,1,n);
for(ll i=1; i<=n; i++){
w[i] = vec[i-1][0], a[i] = vec[i-1][1], b[i] = vec[i-1][2];
val[i] = a[i]-b[i]; // kalo sendiri
if(i%2) ODD.upd(1,1,n,i,val[i]);
else EV.upd(1,1,n,i,val[i]);
mn += val[i];
ALL += b[i];
}
for(ll i=1; i+1<=n; i++)
edge.pb({w[i+1]-w[i], i});
for(ll i=1; i+2<=n; i++){
two.pb({w[i+2]-w[i], i});
// cout << w[i+2]-w[i] << ' ' << i << " i\n";
}
sort(edge.begin(), edge.end());
sort(two.begin(), two.end());
vector<pii> que;
for(ll i=1; i<=q; i++) que.pb({E[i-1], i});
sort(que.begin(), que.end());
A.bd(1,1,n); LE.bd(); RI.bd();
ll e=0, t=0; // yg blm diupdate
for(auto [dis, idx] : que){
while(e<edge.size() && edge[e].fi <= dis){
ll idx = edge[e].se;
// merge idx, idx+1
// cout <<mn << ' '<<idx <<" i\n";
ll lef = LE.f(idx), rig = RI.f(idx+1);
mn -= calc(lef, idx); mn -= calc(idx+1, rig);
LE.mer(idx+1, idx); RI.mer(idx, idx+1);
mn += calc(lef, rig);
e++;
}
while(t<two.size() && two[t].fi <= dis){
ll idx = two[t].se;
// update idx+1
// cout << mn << ' ' << idx+1 << " idx\n";
ll lef = LE.f(idx+1), rig = RI.f(idx+1);
mn -= calc(lef, rig);
A.upd(1,1,n,idx+1,val[idx+1]);
mn += calc(lef, rig);
t++;
}
// l sampe r, kalo odd -> buang yg paling minimum di A
ans[idx] = ALL+mn;
}
for(ll i=1; i<=q; i++) ANS.pb(ans[i]);
return ANS;
}
