#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size(), Q = L.size();
if (N <= 5000 && Q <= 5000) {
vector<ll> ans(Q, inf);
for (int i = 0; i < Q; i++) {
vector<int> stk;
vector<ll> A(N);
for (int j = L[i]; j <= R[i]; j++) {
while (!stk.empty() && H[stk.back()] <= H[j]) {
stk.pop_back();
}
if (stk.empty()) {
A[j] = 1LL * H[j] * (j - (L[i] - 1));
} else {
A[j] = 1LL * H[j] * (j - stk.back()) + A[stk.back()];
}
stk.push_back(j);
}
stk.clear();
vector<ll> B(N);
for (int j = R[i]; j >= L[i]; j--) {
while (!stk.empty() && H[stk.back()] <= H[j]) {
stk.pop_back();
}
if (stk.empty()) {
B[j] = 1LL * H[j] * ((R[i] + 1) - j);
} else {
B[j] = 1LL * H[j] * (stk.back() - j) + B[stk.back()];
}
stk.push_back(j);
}
for (int j = L[i]; j <= R[i]; j++) {
ans[i] = min(ans[i], A[j] + B[j] - H[j]);
}
}
return ans;
}
vector<int> two;
for (int i = 0; i < N; i++) {
if (H[i] == 2) {
two.push_back(i);
}
}
int M = two.size();
int lg = __lg(M);
vector st(M, vector<int>(lg + 1));
for (int i = 1; i < M; i++) {
st[i][0] = two[i] - two[i - 1] - 1;
}
for (int j = 0; j < lg; j++) {
for (int i = 0; i + (2 << j) <= M; i++) {
st[i][j + 1] = max(st[i][j], st[i + (1 << j)][j]);
}
}
auto query = [&](int l, int r) {
if (l == r) {
return 0;
}
int k = __lg(r - l);
return max(st[l][k], st[r - (1 << k)][k]);
};
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
int l = lower_bound(two.begin(), two.end(), L[i]) - two.begin();
int r = upper_bound(two.begin(), two.end(), R[i]) - two.begin() - 1;
if (l == M || two[l] > R[i]) {
ans[i] = R[i] - L[i] + 1;
continue;
}
ans[i] = max(ans[i], two[l] - L[i]);
ans[i] = max(ans[i], R[i] - two[r]);
ans[i] = max(ans[i], query(l + 1, r + 1));
ans[i] = 2 * (R[i] - L[i] + 1) - ans[i];
}
vector<ll> lans(Q);
for (int i = 0; i < Q; i++) {
lans[i] = ans[i];
}
return lans;
}
