#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
struct Node {
ll left, right, total;
bool full;
};
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
ll n = h.size(), q = l.size();
vector<ll> res;
//
res.resize(q);
ll pow2 = 1 << (int)ceil(log2(n));
vector<Node> seg(2 * pow2);
for (int i = 0; i < n; i++) {
seg[pow2 + i].left = seg[pow2 + i].right = seg[pow2 + i].total = seg[pow2 + i].full = h[i] & 1;
}
for (int i = pow2 - 1; i > 0; i--) {
seg[i].left = seg[2*i].left;
seg[i].right = seg[2*i+1].right;
if (seg[2*i].full) seg[i].left += seg[2*i+1].left;
if (seg[2*i+1].full) seg[i].right += seg[2*i].left;
seg[i].total = max({seg[i].left, seg[i].right, seg[2*i].total, seg[2*i+1].total, seg[2*i].right + seg[2*i+1].left});
seg[i].full == seg[2*i].full && seg[2*i+1].full;
}
while (q--) {
res[q] = 2 * (r[q] - l[q] + 1);
int low = pow2 + l[q], high = pow2 + r[q];
Node nd;
nd.left = nd.right = 0;
ll mx = 0;
while (low <= high) {
if (low & 1) {
mx = max(mx, seg[low].total);
mx = max(mx, nd.left + seg[low].left);
if (seg[low].full) {
nd.left += seg[low].right;
}
else {
nd.left = seg[low].right;
}
low++;
}
if (!(high & 1)) {
mx = max(mx, seg[high].total);
mx = max(mx, nd.right + seg[high].right);
if (seg[high].full) {
nd.right += seg[high].left;
}
else {
nd.right = seg[high].left;
}
high--;
}
low >>= 1; high >>= 1;
}
mx = max(mx, nd.left + nd.right);
res[q] -= mx;
}
//
return res;
}
