#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
struct artef
{
long long w,a,b;
} ar[MAXN];
int n,Q;
bool cmp(artef a, artef b)
{
return a.w<b.w;
}
struct event
{
int ind;
long long rzl;
bool edno;
};
bool cmp2(event a, event b)
{
if (a.rzl==b.rzl) return a.edno>b.edno;
return a.rzl<b.rzl;
}
long long smetka=0;
long long seg[4*MAXN][3];
void Initialise(int ind, int l, int r)
{
if (l==r)
{
seg[ind][2]=LONG_LONG_MAX;
seg[ind][l%2]=ar[l].a-ar[l].b;
seg[ind][1-l%2]=LONG_LONG_MAX;
//cout<<l<<" "<<(l%2)<<" "<<(1-l%2)<<" "<<seg[ind][l%2]<<" "<<ind<<" t\n";
return;
}
int mid=(l+r)/2;
Initialise(ind*2,l,mid);
Initialise(ind*2+1,mid+1,r);
seg[ind][0]=min(seg[ind*2][0],seg[ind*2+1][0]);
seg[ind][1]=min(seg[ind*2][1],seg[ind*2+1][1]);
seg[ind][2]=min(seg[ind*2][2],seg[ind*2+1][2]);
}
void Update(int ind, int l, int r, int pos, long long st, int id)
{
if (l==r)
{
seg[ind][id]=st;
return;
}
int mid=(l+r)/2;
if (pos<=mid) Update(ind*2,l,mid,pos,st,id);
else Update(ind*2+1,mid+1,r,pos,st,id);
seg[ind][id]=min(seg[ind*2][id],seg[ind*2+1][id]);
}
long long mnn;
void Query(int ind, int l, int r, int ql, int qr, int id)
{
if (ql<=l && qr>=r)
{
//if (ql==3 && qr==3) cout<<ind<<" "<<l<<" "<<r<<" "<<seg[ind][id]<<"\n";
mnn=min(mnn,seg[ind][id]);
return;
}
int mid=(l+r)/2;
if (ql<=mid) Query(ind*2,l,mid,ql,qr,id);
if (qr>=mid+1) Query(ind*2+1,mid+1,r,ql,qr,id);
}
int par[MAXN];
int gol[MAXN];
int lqv[MAXN];
int fat(int x)
{
if (par[x]==x) return x;
par[x]=fat(par[x]);
return par[x];
}
long long pref[MAXN];
long long cost(int l, int r)
{
//cout<<l<<" "<<r<<"\n";
long long suma=pref[r];
if (l!=0) suma-=pref[l-1];
//cout<<suma<<"\n";
if ((r-l+1)%2==1)
{
mnn=LONG_LONG_MAX;
Query(1,0,n-1,l,r,l%2);
Query(1,0,n-1,l,r,2);
//cout<<mnn<<" "<<(l%2)<<"x\n";
suma+=mnn;
}
//cout<<suma<<"\n";
return suma;
}
void obedini(int x)
{
///obedinqvame x i x+1
int y=fat(x);
int z=fat(x+1);
smetka-=cost(x-gol[y]+1,x);
smetka-=cost(x+1,x+gol[z]);
smetka+=cost(x-gol[y]+1,x+gol[z]);
gol[z]+=gol[y];
lqv[z]=lqv[y];
par[y]=z;
}
void uvelichi(int x)
{
x++;
int y=fat(x);
//cout<<lqv[y]<<" "<<gol[y]<<" dada\n";
smetka-=cost(lqv[y],lqv[y]+gol[y]-1);
//cout<<"pochva "<<x<<"\n";
Update(1,0,n-1,x,ar[x].a-ar[x].b,2);
//cout<<"svyrshi "<<x<<"\n";
smetka+=cost(lqv[y],lqv[y]+gol[y]-1);
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
n=W.size();
Q=E.size();
for (int q=0;q<n;q++)
{
ar[q]={W[q],A[q],B[q]};
}
sort(ar,ar+n,cmp);
vector<event> syb;
for (int q=0;q<n-1;q++)
{
syb.push_back({q,ar[q+1].w-ar[q].w,1});
}
for (int q=0;q<n-2;q++)
{
syb.push_back({q,ar[q+2].w-ar[q].w,0});
}
sort(syb.begin(),syb.end(),cmp2);
vector<pair<int,int>> qu;
for (int q=0;q<Q;q++)
{
qu.push_back({E[q],q});
}
sort(qu.begin(),qu.end());
pref[0]=ar[0].b;
for (int q=1;q<n;q++) pref[q]=pref[q-1]+ar[q].b;
for (int q=0;q<n;q++) smetka+=ar[q].a;
//cout<<smetka<<"\n";
for (int q=0;q<n;q++) par[q]=q;
for (int q=0;q<n;q++) gol[q]=1;
for (int q=0;q<n;q++) lqv[q]=q;
Initialise(1,0,n-1);
vector<long long> otg(Q);
int cure=0;
for (int curq=0;curq<Q;curq++)
{
while (cure<syb.size() && syb[cure].rzl<=qu[curq].first)
{
//cout<<syb[cure].ind<<"\n";
if (syb[cure].edno)
{
obedini(syb[cure].ind);
}
else
{
uvelichi(syb[cure].ind);
}
cure++;
}
otg[ qu[curq].second ]=smetka;
}
return otg;
}
