#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const ll maxn=1e5+5,inf=2e9;
ll n;
struct segtree{
vector<ll>d;
void init(ll n){
d.resize(4*n);
build(1,0,n-1);
}
void build(ll v,ll l,ll r){
if(l==r){
d[v]=inf;
return;
}
ll m=(l+r)>>1;
build(v*2,l,m);
build(v*2+1,m+1,r);
d[v]=min(d[v*2],d[v*2+1]);
}
ll query(ll v,ll l,ll r,ll L,ll R){
if(L>R||l>R||L>r){
return inf;
}
if(L<=l&&r<=R){
return d[v];
}
ll m=(l+r)>>1;
return min(query(v*2,l,m,L,R),query(v*2+1,m+1,r,L,R));
}
void update(ll v,ll l,ll r,ll pos,ll val){
if(r<pos||pos<l){
return;
}
if(l==r){
d[v]=val;
return;
}
ll m=(l+r)>>1;
update(v*2,l,m,pos,val);
update(v*2+1,m+1,r,pos,val);
d[v]=min(d[v*2],d[v*2+1]);
}
};
segtree sg,odd,even;
ll sum[maxn];
ll calc(ll l,ll r){
ll res=sum[r+1]-sum[l];
if((r-l+1)%2==1){
ll mn=sg.query(1,0,n-1,l,r);
if(l%2==0) mn=min(mn,even.query(1,0,n-1,l,r));
if(l%2==1) mn=min(mn,odd.query(1,0,n-1,l,r));
res+=mn;
}
return res;
}
vector<long long>calculate_costs(vector<int>w,vector<int>a,vector<int>b,vector<int>e){
vector<ll>W,A,B,E;
for(ll i=0;i<w.size();i++){
W.pb(w[i]);
A.pb(a[i]);
B.pb(b[i]);
}
for(ll i=0;i<e.size();i++){
E.pb(e[i]);
}
vector<array<ll,3>>box;
ll N=W.size(),Q=E.size();
n=N;
for(ll i=0;i<N;i++){
box.pb({W[i],A[i],B[i]});
}
sum[0]=0;
sort(all(box));
for(ll i=0;i<N;i++){
sum[i+1]=sum[i]+(ll)box[i][2];
}
sg.init(N);
odd.init(N);
even.init(N);
for(ll i=1;i<N-1;i++){
sg.update(1,0,N-1,i,box[i][1]-box[i][2]);
}
for(ll i=0;i<N;i++){
if(i%2==1){
odd.update(1,0,N-1,i,box[i][1]-box[i][2]);
}
else{
even.update(1,0,N-1,i,box[i][1]-box[i][2]);
}
}
vector<array<ll,3>>event;
for(ll i=1;i<N;i++){
event.pb({box[i][0]-box[i-1][0],-2,i});
}
for(ll i=2;i<N;i++){
event.pb({box[i][0]-box[i-2][0],-1,i});
}
for(ll i=0;i<Q;i++){
event.pb({E[i],0,i});
}
sort(rall(event));
ll ans=0;
map<pair<ll,ll>,ll>value;
set<pair<ll,ll>>range;
range.insert({0,N-1});
range.insert({N,N});
value[{0,N-1}]=ans;
range.insert({N,N});
vector<ll>answer(Q);
set<pair<ll,ll>>new_range;
vector<ll>idx;
new_range.insert({0,N-1});
for(auto [_,t,i]:event){
if(t==0){
for(auto [l,r]:new_range){
ll val=calc(l,r);
value[{l,r}]=val;
ans+=val;
}
for(ll i:idx){
auto it=range.upper_bound({i,N});
it--;
ll l=(*it).ff,r=(*it).ss;
ll val=calc(l,r);
ans-=value[{l,r}];
value[{l,r}]=val;
ans+=val;
}
new_range.clear();
idx.clear();
answer[i]=ans;
}
if(t==-1){
i--;
sg.update(1,0,N-1,i,inf);
idx.pb(i);
}
if(t==-2){
auto it=range.upper_bound({i,N});
it--;
pair<ll,ll>p=*it;
range.erase(it);
ll l=p.ff,r=p.ss;
new_range.erase({l,r});
ans-=value[{l,r}];
range.insert({l,i-1});
range.insert({i,r});
new_range.insert({l,i-1});
new_range.insert({i,r});
}
}
return answer;
}
