#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000LL;
ll n, m, q, k, x, y;
struct segtree {
ll n;
vector<ll> tr;
void build(ll x, ll l, ll r, vector<ll> &v) {
if (l == r) {
tr[x] = v[l];
return;
}
ll mid = (r + l) / 2;
build(x * 2 + 1, l, mid, v);
build(x * 2 + 2, mid + 1, r, v);
tr[x] = max(tr[x * 2 + 1], tr[x * 2 + 2]);
}
segtree(vector<ll> &v) {
n = v.size();
tr.resize(n * 4);
build(0, 0, n - 1, v);
}
ll get(ll x, ll l, ll r, ll L, ll R) {
if (r < l) {
return -INF;
}
if (r < L) {
return -INF;
}
if (R < l) {
return -INF;
}
if (R < L) {
return -INF;
}
if (L <= l && r <= R) {
return tr[x];
}
ll mid = (r + l) / 2;
return max(get(x * 2 + 1, l, mid, L, R), get(x * 2 + 2, mid + 1, r, L, R));
}
};
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
vector<ll> ans(q);
if (n <= 5000 && q <= 5000) {
for (int i = 0; i < q; i++) {
vector< pair<ll, ll> > st;
vector<ll> v(n);
ll ans1 = 0;
for (int j = L[i]; j <= R[i]; j++) {
pair<ll, ll> p = {H[j], 1};
while (st.size() > 0 && st[st.size() - 1].first <= p.first) {
ans1 -= st[st.size() - 1].first * st[st.size() - 1].second;
p.second += st[st.size() - 1].second;
st.pop_back();
}
ans1 += p.first * p.second;
st.push_back(p);
v[j] = ans1;
// cout << ans1 << '\n';
}
ans1 = 0;
st.clear();
for (int j = R[i]; j >= L[i]; j--) {
pair<ll, ll> p = {H[j], 1};
while (st.size() > 0 && st[st.size() - 1].first <= p.first) {
ans1 -= st[st.size() - 1].first * st[st.size() - 1].second;
p.second += st[st.size() - 1].second;
st.pop_back();
}
ans1 += p.first * p.second;
st.push_back(p);
v[j] += ans1;
// cout << ans1 << '\n';
}
ans[i] = INF;
for (int j = L[i]; j <= R[i]; j++) {
ans[i] = min(ans[i], v[j] - H[j]);
}
}
}
else {
vector<ll> l(n);
vector<ll> r(n);
l[0] = (H[0] == 1 ? 1 : 0);
for (int i = 1; i < n; i++) {
l[i] = 0;
if (H[i] == 1) {
l[i] = l[i - 1] + 1;
}
}
r[n - 1] = (H[n - 1] == 1 ? 1 : 0);
for (int i = n - 2; i >= 0; i--) {
r[i] = 0;
if (H[i] == 1) {
r[i] = r[i + 1] + 1;
}
}
segtree sg(l);
for (int i = 0; i < q; i++) {
ans[i] = max((ll)(R[i] - L[i] + 1), (R[i] - L[i] + 1) * 2 - max({r[L[i]], l[R[i]], sg.get(0, 0, n - 1, L[i] + r[L[i]], R[i] - l[R[i]])}));
}
}
return ans;
}
