#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct range
{
int l, r = -1;
bool operator<(const range other) const
{
if (r - l > other.r - other.l)
return true;
return r - l == other.r - other.l && l < other.l;
}
bool operator==(const range other) const
{
return l == other.l && r == other.r;
}
};
struct node
{
vector<range> v;
};
node merge(node a, node b)
{
a.v.insert(a.v.end(), b.v.begin(), b.v.end());
sort(a.v.begin(), a.v.end());
for (int i = a.v.size() - 2; i >= 0; i--)
{
if (a.v[i] == a.v[i+1])
{
a.v.erase(a.v.begin() + i + 1);
}
}
a.v.resize(3);
return {a.v};
}
node emptyNode = {{{0, -1}, {0, -1}, {0, -1}}};
int N, nt = 1;
vector<node> st;
node getRange(int l, int r, int k, int x, int y)
{
if (r < x || l > y) return emptyNode;
if (x >= l && y <= r) return st[k];
int c = (x + y) / 2;
return merge(getRange(l, r, k*2, x, c), getRange(l, r, k*2|1, c+1, y));
}
ll valueOf(range n, int l, int r)
{
return min(n.r, r) - max(n.l, l);
}
ll solve(int l, int r)
{
node best = getRange(l, r, 1, 0, nt - 1);
return max({valueOf(best.v[0], l, r), valueOf(best.v[1], l, r), valueOf(best.v[2], l, r)});
}
void makeST(vector<int>&H)
{
vector<range> v;
int last = N;
for (int i = 0; i < N; i++)
{
if (H[i] == 2) continue;
if (last == N)
last = i;
if (H[i+1] == 2)
{
v.push_back({last, i});
last = N;
}
}
while (nt < N)
nt <<= 1;
st = vector<node>(2 * nt, {vector<range>(3)});
for (auto r : v)
{
for (int i = r.l; i <= r.r; i++)
st[nt+i].v[0] = r;
}
for (int i = nt - 1; i >= 1; i--)
st[i] = merge(st[i*2], st[i*2|1]);
/*for (int i = 1; i < 2 * nt; i++)
{
cerr << i << " {("<< st[i].v[0].l << ", " << st[i].v[0].r << "), ("
<< st[i].v[1].l << ", " << st[i].v[1].r << "), ("
<< st[i].v[2].l << ", " << st[i].v[2].r << ")}\n";
}*/
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
const int Q = L.size();
N = H.size();
H.push_back(2);
makeST(H);
vector<ll> C;
for (int q = 0; q < Q; q++)
{
C.push_back(2 * (R[q] - L[q] + 1) - solve(L[q], R[q]) - 1);
}
return C;
}
