#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
long long aint[4*N];
long long lazy[4*N];
void propag(int nod,int l, int r){
aint[nod] += lazy[nod];
if(l != r){
lazy[2*nod] += lazy[nod];
lazy[2*nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
long long computemin(long long a, long long b){
if(a == 0 && b== 0)
return 0;
if(a == 0)
return b;
if(b == 0)
return a;
return min(a, b);
}
void update(int nod,int l, int r,int ul, int ur, long long val){
propag(nod, l, r);
if(l > ur || r < ul || ul > ur)
return;
if(ul <= l && r <= ur){
lazy[nod] += val;
propag(nod, l, r);
return;
}
int mid = (l + r)/2;
update(2*nod, l, mid, ul, ur, val);
update(2*nod + 1, mid+1, r, ul, ur, val);
aint[nod] = computemin(aint[2*nod], aint[2*nod + 1]);
}
long long query(int nod,int l, int r,int ql, int qr){
propag(nod, l, r);
if(l > qr || r < ql || aint[nod] == 0 )
return LLONG_MAX;
if(ql <= l && r<= qr){
return aint[nod];
}
int mid = (l + r)/2;
long long ls = query(2*nod, l, mid, ql, qr);
long long rs = query(2*nod + 1, mid + 1, r, ql, qr);
return min(ls, rs);
}
long long dp[N];
struct blocks{
int t;
int tip;
};
blocks v[N];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int cnt = 0;
for(int i = 0,j = 0; i < r.size() || j < b.size();){
if(i == r.size())
v[++cnt] = {b[j], 2}, j++;
else if(j == b.size())
v[++cnt] = {r[i], 1}, i++;
else if(r[i] < b[j])
v[++cnt] = {r[i], 1}, i++;
else
v[++cnt] = {b[j], 2}, j++;
}
int n = cnt;
vector<int> cur, prev;
cur.push_back(1);
dp[1] = 1LL<<60;
for(int i=2; i<=n;i++){
if(v[i].tip == v[i -1].tip){
cur.push_back(i);
if(prev.empty()){
dp[i] = 1LL<<60;
continue;
}
int lstp = prev[prev.size() - 1], frstp = prev[0];
long long adg1 = v[i].t - v[lstp].t; // adaugam pe intervalul unde se modifica si la mijloc => nr de b uri devine mai mare ca nr de rosii
int nrb = cur.size();
update(1, 1, n, max(frstp, lstp - nrb + 2),lstp, adg1);
long long adg2 = v[i].t - v[lstp + 1].t;
update(1, 1, n, frstp, max(frstp, lstp - nrb + 2) - 1, adg2);
}
else{
swap(cur, prev);
cur.clear();
cur.push_back(i);
long long scor = 0;
for(int j = prev.size() - 1; j >=0; j--){
scor += v[i].t - v[prev[j]].t;
long long dpadg = dp[prev[j] - 1];
if(prev.size() == 1){
dpadg = min(dp[prev[j]-1], dp[prev[j]]);
}
update(1, 1, n, prev[j], prev[j], dpadg + scor);
}
}
int lstp = prev[prev.size() - 1], frstp = prev[0];
dp[i] = query(1, 1, n, frstp, lstp);
}
return dp[n];
}
