#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct Node {
int val, le, ri;
};
Node vd;
Node invalid;
struct DSU {
vector<int> rank, parent;
vector<int> left, right;
DSU(int n) {
rank.assign(n, 1);
parent.resize(n);
left.resize(n);
right.resize(n);
for (int i=0; i<n; i++) {
parent[i] = i;
left[i] = i;
right[i] = i;
}
}
int find(int n) {
return (n == parent[n] ? n : parent[n] = find(parent[n]));
}
void unite(int n1, int n2) {
int p1 = find(n1);
int p2 = find(n2);
if (rank[p1] >= rank[p2]) {
rank[p1] += rank[p2];
parent[p2] = p1;
left[p1] = min(left[p1], left[p2]);
right[p1] = max(right[p1], right[p2]);
}
else {
rank[p2] += rank[p1];
parent[p1] = p2;
right[p2] = max(right[p1], right[p2]);
left[p2] = min(left[p1], left[p2]);
}
}
};
struct SegTree {
vector<Node> tree;
SegTree(int n) {
tree.assign(4*n, vd);
}
void query(int p, int l, int r, int i, int x, int lee, int rii) {
if (l > i || r < i) return;
if (l==r && r==i) {
tree[p].val = x;
tree[p].le = lee;
tree[p].ri = rii;
}
else {
int m = (l+r)/2;
query(2*p, l, m, i, x, lee, rii);
query(2*p+1, m+1, r, i, x, lee, rii);
Node i1 = tree[2*p];
Node i2 = tree[2*p+1];
if (i1.val > i2.val) {
tree[p].val = i1.val;
tree[p].le = i1.le;
tree[p].ri = i1.ri;
}
else {
tree[p].val = i2.val;
tree[p].le = i2.le;
tree[p].ri = i2.ri;
}
}
}
Node rmq(int p, int l, int r, int i, int j) {
if (i > j) return invalid;
if (l > j || r < i) return invalid;
if (i <= l && r <= j) {
return tree[p];
}
else {
int m = (l+r)/2;
Node i1 = rmq(2*p, l, m, i, j);
Node i2 = rmq(2*p+1, m+1, r, i, j);
if (i1.val == -1) return i2;
if (i2.val == -1) return i1;
if (i1.val > i2.val) {
return i2;
}
else {
return i1;
}
}
}
};
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
vd.val = 0;
vd.le = 0;
vd.ri = 0;
invalid.val = -1;
int N = H.size();
int Q = L.size();
vector<int> a(N);
vector<pii> segm(N);
DSU dsu(N);
SegTree st(N);
for(int i=0; i<N-1; i++) {
if (H[i] == H[i+1] && H[i] == 1) {
dsu.unite(i, i+1);
}
}
for (int i=0; i<N; i++) {
if (H[i] == 2) dsu.rank[i] = 0;
}
for (int i=0; i<N; i++) {
int p = dsu.find(i);
a[i] = dsu.rank[p];
segm[i].first = dsu.left[p];
segm[i].second = dsu.right[p];
}
for (int i=0; i<N; i++) {
st.query(1, 0, N-1, i, a[i], segm[i].first, segm[i].second);
}
vector<ll> ans(Q);
for (int i=0; i<Q; i++) {
int caso1, caso2, caso3;
caso1 = caso2 = caso3 = 0;
Node i1 = st.rmq(1, 0, N-1, L[i], R[i]);
int l = i1.le;
int r = i1.ri;
caso1 = i1.val;
if (r >= R[i] && l <= L[i] && i1.val != 0) {
ans[i] = R[i]-L[i]+1;
continue;
}
if (l < L[i]) {
l = L[i];
caso1 = (r-l+1);
Node i2 = st.rmq(1, 0, N-1, r+1, R[i]);
int lee = i2.le;
int ree = i2.ri;
caso2 = i2.val;
if (ree > R[i]) {
ree = R[i];
caso2 = (ree-lee+1);
Node i3 = (st.rmq(1, 0, N-1, r+1, lee-1));
caso3 = i3.val;
}
}
if (r > R[i]) {
r = R[i];
caso1 = (r-l+1);
Node i2 = st.rmq(1, 0, N-1, L[i], l-1);
int lee = i2.le;
int ree = i2.ri;
caso2 = i2.val;
if (lee < L[i]) {
lee = L[i];
caso2 = (ree-lee+1);
Node i3 = st.rmq(1, 0, N-1, ree+1, l-1);
caso3 = i3.val;
}
}
int mx = max({
caso1, caso2, caso3
});
ans[i] = 2*(R[i]-L[i]+1) - mx;
}
return ans;
}
