#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
struct segtree_basic {
struct node {
int lazyval, mi, ma, sum; char lazytag;
int len; // not changing
};
int stok;
vector<node> st;
void bu(int l, int r, int idx) {
st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
st[idx].lazytag = '?';
st[idx].len = r - l + 1;
if(l == r) {
return;
}
int mid = (l + r) >> 1;
bu(l, mid, 2*idx+1);
bu(mid+1, r, 2*idx+2);
}
void push_down(int idx) {
if(st[idx].lazytag == '?') return;
if(st[idx].lazytag == ':') {
st[2*idx+1].lazyval = st[idx].lazyval;
st[2*idx+1].mi = st[idx].lazyval;
st[2*idx+1].ma = st[idx].lazyval;
st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
st[2*idx+1].lazytag = ':';
st[2*idx+2].lazyval = st[idx].lazyval;
st[2*idx+2].mi = st[idx].lazyval;
st[2*idx+2].ma = st[idx].lazyval;
st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
st[2*idx+2].lazytag = ':';
}
else {
st[2*idx+1].lazyval += st[idx].lazyval;
st[2*idx+1].mi += st[idx].lazyval;
st[2*idx+1].ma += st[idx].lazyval;
st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
st[2*idx+2].lazyval += st[idx].lazyval;
st[2*idx+2].mi += st[idx].lazyval;
st[2*idx+2].ma += st[idx].lazyval;
st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
}
st[idx].lazytag = '?';
st[idx].lazyval = 0;
}
void push_up(int idx) {
st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
}
void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
if(l <= constl && constr <= r) {
st[idx].lazyval = val;
st[idx].mi = val;
st[idx].ma = val;
st[idx].sum = val * st[idx].len;
st[idx].lazytag = ':';
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
else {
u1(l, r, constl, mid, 2*idx+1, val);
u1(l, r, mid+1, constr, 2*idx+2, val);
}
push_up(idx);
}
void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
if(l <= constl && constr <= r) {
st[idx].lazyval += val;
st[idx].mi += val;
st[idx].ma += val;
st[idx].sum += val * st[idx].len;
st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
else {
u2(l, r, constl, mid, 2*idx+1, val);
u2(l, r, mid+1, constr, 2*idx+2, val);
}
push_up(idx);
}
int qu1(int l, int r, int constl, int constr, int idx) { // range min
if(l <= constl && constr <= r) return st[idx].mi;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid + 1) return qu1(l, r, constl, mid, 2*idx+1);
else {
return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
}
}
int qu2(int l, int r, int constl, int constr, int idx) { // range max
if(l <= constl && constr <= r) return st[idx].ma;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid + 1) return qu2(l, r, constl, mid, 2*idx+1);
else {
return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
}
}
int qu3(int l, int r, int constl, int constr, int idx) { // range sum
if(l <= constl && constr <= r) return st[idx].sum;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu3(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid + 1) return qu3(l, r, constl, mid, 2*idx+1);
else {
return qu3(l, r, constl, mid, 2*idx+1) + qu3(l, r, mid+1, constr, 2*idx+2);
}
}
int qu4(int l, int r, int constl, int constr, int idx, int val) { // first at least v
if(l <= constl && constr <= r) {
if(st[idx].ma < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+1].ma >= val) constr = mid, idx = 2*idx + 1;
else constl = mid+1, idx = 2*idx + 2;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu4(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu4(l, r, constl, mid, 2*idx+1, val);
else {
int lchild = qu4(l, r, constl, mid, 2*idx+1, val);
if(lchild != -1) return lchild;
return qu4(l, r, mid+1, constr, 2*idx+2, val);
}
}
int qu5(int l, int r, int constl, int constr, int idx, int val) { // first at most v
if(l <= constl && constr <= r) {
if(st[idx].mi > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+1].mi <= val) constr = mid, idx = 2*idx + 1;
else constl = mid+1, idx = 2*idx + 2;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu5(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu5(l, r, constl, mid, 2*idx+1, val);
else {
int lchild = qu5(l, r, constl, mid, 2*idx+1, val);
if(lchild != -1) return lchild;
return qu5(l, r, mid+1, constr, 2*idx+2, val);
}
}
int qu6(int l, int r, int constl, int constr, int idx, int val) { // last at least v
if(l <= constl && constr <= r) {
if(st[idx].ma < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+2].ma >= val) constl = mid+1, idx = 2*idx + 2;
else constr = mid, idx = 2*idx + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu6(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu6(l, r, constl, mid, 2*idx+1, val);
else {
int rchild = qu6(l, r, mid+1, constr, 2*idx+2, val);
if(rchild != -1) return rchild;
return qu6(l, r, constl, mid, 2*idx+1, val);
}
}
int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
if(l <= constl && constr <= r) {
if(st[idx].mi > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
else constr = mid, idx = 2*idx + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
else {
int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
if(rchild != -1) return rchild;
return qu7(l, r, constl, mid, 2*idx+1, val);
}
}
public:
void resize(int k) {
st.resize(4*k + 10);
stok = k;
bu(0, k, 0);
}
void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
int query_max(int l, int r) { return qu2(l, r, 0, stok, 0); }
int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); }
int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
};
long long ps[MAXN];
long long f(int l1, int r1, int l2, int r2) {
long long cntB = r2 - l2 + 1;
long long cntR = r1 - l1 + 1;
long long sumB = ps[r2] - ps[l2 - 1];
long long sumR = ps[r1] - ps[l1 - 1];
if(cntR <= cntB) {
return sumB - sumR - (cntB - cntR) * (ps[r1] - ps[r1 - 1]);
// sumB - sumR - cntB * a[r1] + cntR * a[r1]
}
else {
return sumB - sumR + (cntR - cntB) * (ps[l2] - ps[l2 - 1]);
}
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<pair<long long, char> > all;
all.push_back({-1, 'N'});
for(int i=0; i<r.size(); i++) all.push_back({r[i], 'R'});
for(int i=0; i<b.size(); i++) all.push_back({b[i], 'B'});
sort(all.begin(), all.end());
int n = all.size() - 1;
long long dp[n+1];
ps[0] = 0;
for(int i=1; i<=n; i++) ps[i] = ps[i-1] + all[i].first;
segtree_basic case1, case2;
case1.resize(n);
case2.resize(n);
dp[0] = 0;
int prv = 0, cur = 0;
long long sumB = 0;
for(int i=1; i<=n; i++) {
dp[i] = 1e16;
if(i == 1) {
cur = 1;
sumB += all[1].first;
}
else {
if(all[i].second != all[i-1].second) {
prv = cur;
cur = 1;
// UPDATE ALL
case1.range_assign(1, n, 0);
case2.range_assign(1, n, 0);
long long sumR = 0, cntR = 0;
for(int j=i-1; j>=i-prv; j--) {
sumR += all[j].first;
cntR++;
case1.range_add(j, j, dp[j-1] - sumR + cntR * all[i-cur].first);
case2.range_add(j, j, dp[j-1] - sumR + cntR * all[i-cur+1].first);
}
sumB = all[i].first;
}
else {
cur = cur + 1;
sumB += all[i].first;
}
}
if(prv == 0) continue;
// prv, cur
// special case
dp[i] = min(dp[i], dp[i - cur] + f(i-cur, i-cur, i-cur+1, i));
long long cntB = cur;
// case 1 prv <= cur
// dp[i] = dp[j-1] + sumB - sumR + cntR * a[i-cur] - cntB * a[i-cur], i-cur-prv+1 to i-cur
dp[i] = min(dp[i], case1.query_min(i-cur-max(prv, cur) + 1, i-cur) + sumB - cntB * all[i-cur].first);
// case 2 prv > cur
// dp[i] = dp[j-1] + sumB - sumR + cntR * a[i-cur+1] - cntB * a[i-cur+1]
if(prv > cur) dp[i] = min(dp[i], case2.query_min(i-cur-prv, i-cur-cur) + sumB - cntB * all[i-cur+1].first);
/*
bool active = 0;
int cntsame = 0, cntdiff = 0;
for(int j=i; j>=1; j--) {
if(all[j].second == all[i].second && active) {
break;
}
if(all[j].second == all[i].second) cntsame++;
if(all[j].second != all[i].second) {
active = 1; // use [j, i], reference dp[j-1]
cntdiff++;
dp[i] = min(dp[i], dp[j-1] + f(j, j+cntdiff-1, j+cntdiff, i));
dp[i] = min(dp[i], dp[j] + f(j, j+cntdiff-1, j+cntdiff, i));
}
}
*/
}
return dp[n];
}
