#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 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];
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<long long> R(Q);
long long otg=0;
for (int q=0;q<n;q++) otg+=B[q];
if (n%2==1)
{
long long bst=2000000000;
for (int q=0;q<n;q++)
{
long long cur=A[q]-B[q];
if (cur<bst) bst=cur;
}
otg+=bst;
}
for (int q=0;q<Q;q++) R[q]=otg;
/*
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;
}*/
return R;
}
