#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
const int lg = 13;
int sp[maxn][lg];
int dp[maxn];
vector <pair <int, int> > inv;
int query (int l, int r) {
int k = log2(r - l + 1);
return max(sp[l][k], sp[r - (1 << k) + 1][k]);
}
vector<int64> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
int n = H.size();
vector<int64> C(Q);
int pt = -1;
for (int i = 0; i < n; i++){
if (H[i] == 2){
if (pt != -1){
inv.push_back({pt, i - 1});
pt = -1;
}
}
else {
if (pt == -1) pt = i;
}
}
int m = inv.size();
for (int i = 0; i < m; i++){
sp[i][0] = inv[i].second - inv[i].first + 1;
}
for (int k = 1; k < lg; k++){
for (int i = 0; i + (1 << k) - 1 < m; i++){
sp[i][k] = max(sp[i][k-1], sp[i + (1 << (k - 1))][k-1]);
}
}
for (int i = 0; i < Q; i++){
int mx = 0;
int l = lower_bound(inv.begin(), inv.end(), make_pair(L[i], -1)) - inv.begin();
int r = upper_bound(inv.begin(), inv.end(), make_pair(R[i] + 1, -1)) - inv.begin();
// [l, r)
if (l != 0) {
mx = max(mx, min(R[i], inv[l-1].second) - max(L[i], inv[l].first) + 1);
}
if (r != 0) {
mx = max(mx, min(R[i], inv[r - 1].second) - max(L[i], inv[r - 1].first) + 1);
}
if (r - 1 >= l) mx = max(mx, query(l, r - 1));
C[i] = (R[i] - L[i] + 1) * 2 - mx;
}
return C;
}
