#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int MXN = 100005;
int arr[MXN];
int segpf[MXN * 4];
int segsf[MXN * 4];
int segans[MXN * 4];
void comb(int ind, int l, int r) {
int m = (r + l) / 2;
segans[ind] = max(segans[ind * 2], segans[ind * 2 + 1]);
segsf[ind] = segsf[ind * 2 + 1];
if (segsf[ind] == r - m) segsf[ind] += segsf[ind * 2];
segpf[ind] = segpf[ind * 2];
if (segpf[ind] == m - l + 1) segpf[ind] += segpf[ind * 2 + 1];
segans[ind] = max(segans[ind], segsf[ind*2] + segpf[ind*2+1]);
}
void build(int ind, int l, int r) {
if (l == r) {
if (arr[l] == 1) {
segpf[ind] = segsf[ind] = segans[ind] = 1;
}
return;
}
int m = (l + r) / 2;
build(ind * 2, l, m);
build(ind * 2 + 1, m+1, r);
comb(ind, l, r);
}
int qpf[MXN * 4];
int qsf[MXN * 4];
int qns[MXN * 4];
void qcomb(int ind, int l, int r) {
int m = (r + l) / 2;
qns[ind] = max(qns[ind * 2], qns[ind * 2 + 1]);
qsf[ind] = qsf[ind * 2 + 1];
if (qsf[ind] == r - m) qsf[ind] += qsf[ind * 2];
qpf[ind] = qpf[ind * 2];
if (qpf[ind] == m - l + 1) qpf[ind] += qpf[ind * 2 + 1];
qns[ind] = max(qns[ind], qsf[ind*2] + qpf[ind*2+1]);
}
void query(int ind, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
qpf[ind] = segpf[ind];
qsf[ind] = segsf[ind];
qns[ind] = segans[ind];
return;
}
if (ql > r || qr < l) {
qpf[ind] = 0;
qsf[ind] = 0;
qns[ind] = 0;
return;
}
int m = (l + r) / 2;
query(ind * 2, l, m, ql, qr);
query(ind * 2 + 1, m+1, r, ql, qr);
qcomb(ind, l, r);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
std::vector<long long> C(Q);
n = H.size();
for (int i=0; i<n; i++) {
arr[i] = H[i];
}
build(1, 0, n-1);
for (int i=0; i<Q; i++) {
query(1, 0, n-1, L[i], R[i]);
C[i] = 2 * (R[i] - L[i] + 1) - qns[1];
}
return C;
}
