#include "nile.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 3e5 + 10;
long long n, q;
long long w[maxn], a[maxn], b[maxn];
long long dp[maxn]; /// best match count
long long r[maxn];
long long ans;
long long pa[maxn], sz[maxn], res[maxn], gl[maxn], gr[maxn];
long long best_odd[maxn], best_even[maxn], bs[maxn];
long long other[maxn];
long long t[maxn * 4], val[maxn];
void build_tree(long long i, long long l, long long r)
{
if(l == r)
{
t[i] = 1e17;
return;
}
long long mid = (l + r)/2;
build_tree(2*i, l, mid);
build_tree(2*i+1, mid+1, r);
t[i] = 1e17;
}
long long ql, qr;
long long query(long long i, long long l, long long r)
{
if(qr < ql)return 1e17;
if(qr < l || ql > r)return 1e17;
if(ql <= l && r <= qr)return t[i];
long long mid = (l + r)/2;
return min(query(2*i, l, mid), query(2*i+1, mid+1, r));
}
long long upos;
void update(long long i, long long l, long long r)
{
if(l == r)
{
// cout << "updated " << val[l] << endl;
t[i] = val[l];
return;
}
long long mid = (l + r)/2;
if(upos <= mid)update(2*i, l, mid);
else update(2*i+1, mid+1, r);
t[i] = min(t[2*i], t[2*i+1]);
}
long long find_leader(long long i)
{
if(pa[i] == i)return i;
return (pa[i] = find_leader(pa[i]));
}
void change(int i, int index)
{long long nowans = res[i];
ans -= nowans;
if(index > gl[i] && index < gr[i])
{
other[i] = min(other[i], val[index]);
res[i] = bs[i];
long long cut = min(best_odd[i], other[i]);
if(sz[i] & 1)res[i] += cut;
}
ans += res[i];
}
void unite(long long i, long long j)
{
i = find_leader(i);
j = find_leader(j);
if(i == j)return;
if(i > j)swap(i, j);
ans -= res[i];
ans -= res[j];
long long lft = sz[i];
sz[i] += sz[j];
pa[j] = i;
gl[i] = min(gl[i], gl[j]);
gr[i] = max(gr[i], gr[j]);
// cout << gl[i] << ' ' << gr[i] << endl;
if(lft & 1)
{
best_even[i] = min(best_even[i], best_odd[j]);
best_odd[i] = min(best_odd[i], best_even[j]);
}
else
{
best_even[i] = min(best_even[i], best_even[j]);
best_odd[i] = min(best_odd[i], best_odd[j]);
}
bs[i] += bs[j];
res[i] = bs[i];
long long cut = best_odd[i];
ql = gl[i] + 1;
qr = gr[i] - 1;
long long newcut = query(1, 0, n-1);
other[i] = newcut;
cut = min(cut, newcut);
if(sz[i] & 1)res[i] += cut;//(sz[i] % 2);
ans += res[i];
}
vector < pair < long long, long long > > u;
void solve()
{
vector < pair < long long, long long > > g;
vector < pair < long long, long long > > v;
for (long long i = 1; i < n; ++ i)
{
long long d = w[i] - w[i-1];
g.push_back(make_pair(d, i-1));
}
for (long long i = 1; i < n-1; ++ i)
{
long long con = w[i+1] - w[i-1];
v.pb(make_pair(con, i));
}
sort(g.begin(), g.end());
sort(v.begin(), v.end());
long long i = 0, j = 0;
for (auto &[dif, pos]: u)
{
while(j < v.size() && v[j].first <= dif)
{
upos = v[j].second;
update(1, 0, n-1);
int lead = find_leader(upos);
change(lead, upos);
j ++;
}
while(i < g.size() && g[i].first <= dif)
{
long long posx = g[i].second;
long long posy = posx + 1;
unite(posx, posy);
i ++;
}
r[pos] = ans;
}
}
struct p
{
long long w, a, b;
p() {};
p(long long _w, long long _a, long long _b)
{
w = _w;
a = _a;
b = _b;
}
};
bool cmp(p p1, p p2)
{
return (p1.w < p2.w);
}
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();
for (long long i = 0; i < n; ++ i)
w[i] = W[i];
for (long long i = 0; i < n; ++ i)
a[i] = A[i];
for (long long i = 0; i < n; ++ i)
b[i] = B[i];
vector < p > g;
for (long long i = 0; i < n; ++ i)
g.pb(p(w[i], a[i], b[i]));
sort(g.begin(), g.end(), cmp);
long long i = 0;
for (auto &[ww, aa, bb]: g)
{
w[i] = ww;
a[i] = aa;
b[i] = bb;
i ++;
}
build_tree(1, 0, n-1);
for (long long i = 0; i < n; ++ i)
{
val[i] = a[i] - b[i];
pa[i] = i;
sz[i] = 1;
res[i] = a[i];
bs[i] = b[i];
other[i] = 1e17;
best_odd[i] = a[i] - b[i];
best_even[i] = 1e17;
gl[i] = i;
gr[i] = i;
ans += a[i];
}
q = (long long)E.size();
vector < long long > result;
for (long long i = 0; i < E.size(); ++ i)
{
u.pb(make_pair(E[i], i));
}
sort(u.begin(), u.end());
solve();
for (long long i = 0; i < q; ++ i)
result.pb(r[i]);
return result;
}
