#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
return a.w<b.w;
}
int par[MAXN];
int gol[MAXN];
bool vkl[MAXN];
int klkV=0;
int ft(int x)
{
if (par[x]==x) return x;
par[x]=ft(par[x]);
return par[x];
}
void dobavi(int x)
{
vkl[x]=1;
gol[x]=1;
klkV+=1;
if (x!=n-2 && vkl[x+1])
{
int y=ft(x+1);
klkV--;
klkV-=(gol[y]+1)/2;
gol[y]++;
par[x]=y;
klkV+=(gol[y]+1)/2;
}
if (x!=0 && vkl[x-1])
{
int y=ft(x);
int z=ft(x-1);
klkV-=(gol[y]+1)/2;
klkV-=(gol[z]+1)/2;
if (gol[y]>gol[z]) swap(y,z);
gol[z]+=gol[y];
par[y]=z;
klkV+=(gol[z]+1)/2;
}
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
int Q = (int)E.size();
n=A.size();
for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
sort(ar,ar+n,cmp);
vector<pair<int,int>> rzl;
for (int q=0;q<n-1;q++)
{
int df=ar[q+1].w-ar[q].w;
rzl.push_back({df,q});
}
sort(rzl.begin(),rzl.end());
vector<long long> R(Q);
vector<pair<int,int>> qu(Q);
for (int q=0;q<Q;q++)
{
qu[q].first=E[q];
qu[q].second=q;
}
sort(qu.begin(),qu.end());
for (int q=0;q<n-1;q++) par[q]=q;
for (int q=0;q<n-1;q++) vkl[q]=0;
int curd=0;
for (int curq=0;curq<Q;curq++)
{
while (curd<n-1 && rzl[curd].first<=qu[curq].first)
{
dobavi(rzl[curd].second);
curd++;
}
R[ qu[curq].second ]=2*klkV+(n-2*klkV)*2;
}
return R;
}
int rr[MAXN],lr[MAXN];
struct state
{
long long namal;
int lsl,rsl;
int lm,rm;
};
bool operator<(state a, state b)
{
return a.namal<b.namal;
}
bool operator>(state a, state b)
{
return a.namal>b.namal;
}
bool sloz[MAXN];
void func()
{
/*
for (int curZ=0;curZ<Q;curZ++)
{
int d=E[curZ];
rr[n-1]=n-1;
for (int q=n-2;q>=0;q--)
{
rr[q]=rr[q+1];
while ((ar[rr[q]].w-ar[q].w)>d) rr[q]--;
}
lr[0]=0;
for (int q=1;q<n;q++)
{
lr[q]=lr[q-1];
while ((ar[q].w-ar[lr[q]].w)>d) lr[q]++;
}
//cout<<d<<"\n";
//for (int q=0;q<n;q++) cout<<lr[q]<<" ";
//cout<<"\n";
//for (int q=0;q<n;q++) cout<<rr[q]<<" ";
//cout<<"\n";
long long otg=0;
for (int q=0;q<n;q++) otg+=ar[q].a;
for (int q=0;q<n;q++) sloz[q]=0;
priority_queue<state> qu;
for (int q=0;q<n;q++)
{
int bst=0,koi=-1;
for (int w=lr[q];w<=rr[q];w++)
{
if (w==q) continue;
if ((ar[w].a-ar[w].b)>bst)
{
bst=ar[w].a-ar[w].b;
koi=w;
}
}
cout<<q<<" "<<koi<<"aa\n";
if (koi==-1) continue;
if (koi<q)
{
qu.push({ar[q].a-ar[q].b+ar[koi].a-ar[koi].b,koi,q,-1,-1});
}
else
{
qu.push({ar[q].a-ar[q].b+ar[koi].a-ar[koi].b,q,koi,-1,-1});
}
}
while (!qu.empty())
{
state tp=qu.top();
qu.pop();
if (sloz[ tp.lsl ] || sloz[ tp.rsl ]) continue;
otg-=tp.namal;
sloz[ tp.lsl ]=1;
sloz[ tp.rsl ]=1;
cout<<tp.namal<<" "<<tp.lsl<<" "<<tp.rsl<<"\n";
int bstr=0,koir=-1;
for (int w=tp.rsl+1;w<=rr[ tp.rsl ];w++)
{
if (sloz[w]) continue;
if ((ar[w].a-ar[w].b)>bstr)
{
bstr=ar[w].a-ar[w].b;
koir=w;
}
}
int bstl=0,koil=-1;
for (int w=tp.lsl-1;w>=lr[tp.lsl];w--)
{
if (sloz[w]) continue;
if ((ar[w].a-ar[w].b)>bstl)
{
bstl=ar[w].a-ar[w].b;
koil=w;
}
}
if (koil==-1 || koir==-1) continue;
qu.push({ar[koil].a-ar[koil].b+ar[koir].a-ar[koir].b,koil,koir,tp.lsl,tp.rsl});
}
cout<<otg<<"\n";
R[curZ]=otg;
}*/
}
