#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
struct Info {
int len, pref, suff, sub;
Info(int len, int pref, int suff, int sub) : len(len), pref(pref), suff(suff), sub(sub) { }
Info(int val) : Info(1, !val, !val, !val) { }
Info() : Info(1, 0, 0, 0) { }
};
Info merge(const Info &a, const Info &b) {
return {a.len + b.len, a.pref + (a.pref == a.len) * b.pref , b.suff + (b.suff == b.len) * a.suff, max({a.sub, b.sub, a.suff + b.pref})};
}
struct SegTree {
vector<Info> arr;
int s;
Info query(int l, int r) {
Info ans_l, ans_r;
for (l += s, r += s; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans_l = merge(ans_l, arr[l++]);
if (r & 1) ans_r = merge(arr[--r], ans_r);
}
return merge(ans_l, ans_r);
}
SegTree(int N, const vector<int> &a) {
s = 1 << (int)ceil(log2(N));
arr.resize(2 * s);
for (int i = 0; i < N; i++) arr[i + s] = Info(a[i]);
for (int i = s - 1; i; i--) arr[i] = merge(arr[2 * i], arr[2 * i + 1]);
}
};
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size();
int Q = L.size();
vector<long long> ans(Q);
if (Q <= 5000 && N <= 5000) {
for (int i = 0; i < Q; i++) {
vector<long long> cost_l(R[i] - L[i] + 2), cost_r(R[i] - L[i] + 2);
stack<pair<int, int>> st;
st.emplace(2e9, R[i] - L[i] + 1);
for (int j = R[i] - L[i]; j >= 0; j--) {
while (st.top().first <= H[j + L[i]]) st.pop();
cost_r[j] = cost_r[st.top().second] + (long long)H[j + L[i]] * (st.top().second - j);
st.emplace(H[j + L[i]], j);
}
while (!st.empty()) st.pop();
st.emplace(2e9, 0);
for (int j = 0; j <= R[i] - L[i]; j++) {
while (st.top().first <= H[j + L[i]]) st.pop();
cost_l[j + 1] = cost_l[st.top().second] + (long long)H[j + L[i]] * (j + 1 - st.top().second);
st.emplace(H[j + L[i]], j + 1);
}
ans[i] = 1e18;
for (int j = 0; j <= R[i] - L[i]; j++) {
ans[i] = min(ans[i], cost_l[j + 1] + cost_r[j] - H[j + L[i]]);
}
}
} else {
SegTree segtree(N, H);
for (int i = 0; i < Q; i++) {
ans[i] = R[i] - L[i] + 1 - segtree.query(L[i], R[i] + 1).sub;
}
}
return ans;
}
