# include <iostream>
# include <vector>
# include <algorithm>
# include <cassert>
# define all(x) x.begin(),x.end()
using namespace std;
# include "nile.h"
//# include "grader.cpp"
const long long INF=1e18;
const int MAX=1e5+11,LOG=20;
int n,q;
long long s;
pair<int,long long> a[MAX];
long long pref[MAX];
int even[MAX][LOG];
int odd[MAX][LOG];
void sparse_table()
{
for(int i=1;i<=n;i++)
{
if(i%2==0)
{
even[i][0]=a[i].second;
odd[i][0]=1e9;
}
else
{
even[i][0]=1e9;
odd[i][0]=a[i].second;
}
}
for(int j=1;j<LOG;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
even[i][j]=min(even[i][j-1],even[i+(1<<(j-1))][j-1]);
odd[i][j]=min(odd[i][j-1],odd[i+(1<<(j-1))][j-1]);
}
}
}
int Even(int l, int r)
{
int j=31-__builtin_clz(r-l+1);
return min(even[l][j],even[r-(1<<j)+1][j]);
}
int Odd(int l, int r)
{
int j=31-__builtin_clz(r-l+1);
return min(odd[l][j],odd[r-(1<<j)+1][j]);
}
int tree[MAX*4];
void build(int v=1, int l=1, int r=n)
{
if(l==r)
{
tree[v]=1e9;
return ;
}
int mid=(l+r)/2;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
tree[v]=min(tree[v*2],tree[v*2+1]);
}
void update(int pos, int v=1, int l=1, int r=n)
{
if(l==r)
{
tree[v]=a[pos].second;
return ;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos,v*2,l,mid);
else update(pos,v*2+1,mid+1,r);
tree[v]=min(tree[v*2],tree[v*2+1]);
}
int query(int le, int ri, int v=1, int l=1, int r=n)
{
if(ri<l or r<le) return 1e9;
if(le<=l and r<=ri) return tree[v];
int mid=(l+r)/2;
return min(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r));
}
long long calc(int l, int r)
{
if((r-l+1)%2==0) return pref[r]-pref[l-1];
int ans=min(a[l].second,a[r].second);
if(l%2==0) ans=min(ans,Even(l,r));
else ans=min(ans,Odd(l,r));
ans=min(ans,query(l,r));
return pref[r]-pref[l-1]-ans;
}
int sz[MAX];
int par[MAX];
int le[MAX];
int ri[MAX];
long long cost[MAX];
void init()
{
for(int i=1;i<=n;i++)
{
sz[i]=1;
par[i]=i;
le[i]=i;
ri[i]=i;
cost[i]=0;
}
}
int root(int u)
{
if(par[u]==u) return u;
else return par[u]=root(par[u]);
}
void unite(int u, int v)
{
u=root(u);
v=root(v);
if(u==v) return ;
if(sz[u]<sz[v]) swap(u,v);
s+=cost[u]+cost[v];
le[u]=min(le[u],le[v]);
ri[u]=max(ri[u],ri[v]);
par[v]=u;
sz[u]+=sz[v];
cost[u]=calc(le[u],ri[u]);
s-=cost[u];
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
n=W.size();q=E.size();
for(int i=0;i<n;i++)
{
a[i+1]={W[i],A[i]-B[i]};
s+=A[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i].second;
vector<pair<int,int>> qrs,items,avail;
vector<long long> Final(q);
for(int i=1;i<n;i++) items.push_back({a[i+1].first-a[i].first,i});
for(int i=2;i<n;i++) avail.push_back({a[i+1].first-a[i-1].first,i});
for(int i=0;i<q;i++) qrs.push_back({E[i],i});
sort(all(items));
sort(all(avail));
sort(all(qrs));
init();
build();
sparse_table();
int ptr=0,ptr2=0;
for(pair<int,int> PA: qrs)
{
int w=PA.first,id=PA.second;
while(ptr<(int)items.size() and items[ptr].first<=w)
{
int x=items[ptr].second;
unite(x,x+1);
ptr++;
//cout<<x<<"->"<<s<<"\n";
}
while(ptr2<(int)avail.size() and avail[ptr2].first<=w)
{
int x=avail[ptr2].second;
update(x);
int rt=root(x);
s+=cost[rt];
cost[rt]=calc(le[rt],ri[rt]);
s-=cost[rt];
ptr2++;
//cout<<x<<"-->"<<s<<"\n";
//if(x==3) cout<<query(3,3)<<"\n";
}
Final[id]=s;
}
return Final;
}
/**
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5 9 1
*/
