#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const ll INF = 1LL << 60;
struct item
{
int l, r, m;
void set(int i) { l = r = m = i; }
};
struct segtree
{
vector<item> arr;
int size;
const item NEUTRAL = {0, 0, 0};
item combine(const item &a, const item &b, int len)
{
return {(a.l == len) ? a.l + b.l : a.l, (b.r == len) ? b.r + a.r : b.r, max(a.r + b.l, max(a.m, b.m))};
}
void init(vector<int> &H)
{
size = 1;
while (size < sz(H))
size *= 2;
arr.resize(2 * size);
for (int i = 0; i < sz(H); ++i)
set(i, (H[i] == 1));
}
void set(int i, int v) { set(i, v, 1, 0, size); }
void set(int i, int v, int x, int lx, int rx)
{
if (rx - lx == 1)
{
arr[x].set(v);
return;
}
int m = (lx + rx) / 2;
if (i < m)
set(i, v, 2 * x, lx, m);
else
set(i, v, 2 * x + 1, m, rx);
arr[x] = combine(arr[2 * x], arr[2 * x + 1], (rx - lx) / 2);
}
int query(int l, int r) { return query(l, r, 1, 0, size).m; }
item query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return arr[x];
if (r <= lx || rx <= l)
return NEUTRAL;
int m = (lx + rx) / 2;
item a = query(l, r, 2 * x, lx, m);
item b = query(l, r, 2 * x + 1, m, rx);
return combine(a, b, (rx - lx) / 2);
}
};
segtree seg;
vi minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
int N = sz(H);
int Q = L.size();
seg.init(H);
vi ans(Q);
for (int j = 0; j < Q; ++j)
{
ans[j] = 2 * (R[j] - L[j] + 1) - seg.query(L[j], R[j] + 1);
}
return ans;
}
