#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)
#define rev(n, i) for (int i = n - 1; i >= 0; i--)
typedef signed i32;
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<vi32> vvi32;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
struct node
{
int cnt = 0, cntl = 0, cntr = 0, sz = 0;
node operator+(node b)
{
int cntl2 = cntl, cntr2 = b.cntr;
if (cntl == sz)
cntl2 += b.cntl;
if (b.cntr == sz)
cntr2 += cntr;
return {max({cnt, b.cnt, cntr + b.cntl}), cntl2, cntr2, sz + b.sz};
};
void operator+=(node b) { *this = *this + b; }
};
vector<node> s;
node query(int i, int l, int r, int ql, int qr)
{
if (qr < l || r < ql)
return {};
if (ql <= l && r <= qr)
return s[i];
int m = (l + r) / 2;
return query(2 * i, l, m, ql, qr) + query(2 * i + 1, m + 1, r, ql, qr);
}
vi minimum_costs(vi32 H, vi32 L, vi32 R)
{
int Q = sz(L);
vi C(Q);
int N = sz(H);
int treeN = 1;
while (treeN < N)
treeN *= 2;
s.assign(2 * treeN, {});
loop(N, i)
{
s[i + treeN].sz = 1;
if (H[i] == 1)
s[i + treeN] = {1, 1, 1, 1};
}
rev(treeN, i)
{
s[i] = s[2 * i] + s[2 * i + 1];
}
for (int j = 0; j < Q; ++j)
{
int l = L[j];
int r = R[j];
C[j] = query(1, 0, treeN - 1, l, r).cnt;
}
return C;
}
