#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct stk {
long long sum = 0;
stack<pii> st;
stk():sum(0){while(!st.empty())st.pop();}
void add(int x) {
int cur = 1;
while(!st.empty() && st.top().first <= x) {
cur += st.top().second;
sum -= 1ll*st.top().first*st.top().second;
st.pop();
}
st.emplace(x, cur);
sum += 1ll*x*cur;
}
} ls, rs;
long long l[5005], r[5005];
struct dat {
int L, R, ans;
bool allone;
dat(){L=R=ans=allone=0;}
dat(int x){allone=L=R=ans=(x==1);}
} segm[400005];
dat operator+(dat a, dat b) {
dat ret;
ret.allone = (a.allone && b.allone);
ret.L = (a.allone ? a.L + b.L : a.L);
ret.R = (b.allone ? b.R + a.R : b.R);
ret.ans = max({a.ans, b.ans, a.R + b.L});
return ret;
}
void build(int idx, int l, int r, vector<int>& ans) {
if(l == r)
segm[idx] = dat(ans[l]);
else {
int mid = (l+r) >> 1;
build(idx*2+1, l, mid, ans);
build(idx*2+2, mid+1, r, ans);
segm[idx] = segm[idx*2+1] + segm[idx*2+2];
}
}
dat qr(int idx, int l, int r, int tl, int tr) {
if(tl <= l && r <= tr) return segm[idx];
if(tr < l || r < tl) return dat();
int mid = (l+r) >> 1;
return qr(idx*2+1, l, mid, tl, tr) + qr(idx*2+2, mid+1, r, tl, tr);
}
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);
if(*max_element(H.begin(), H.end()) <= 2) {
int l=-1,r=-1;
build(0, 0, H.size()-1, H);
for(int cq=0;cq<Q;cq++) {
C[cq] = 2*(R[cq]-L[cq]+1) - qr(0, 0, H.size()-1, L[cq], R[cq]).ans;
}
return C;
}
for (int j = 0; j < Q; ++j) {
C[j] = __LONG_LONG_MAX__;
ls = stk(); rs = stk();
for(int i=L[j];i<=R[j];i++) {
ls.add(H[i]); l[i] = ls.sum;
}
for(int i=R[j];i>=L[j];i--) {
rs.add(H[i]); r[i] = rs.sum;
}
for(int i=L[j];i<=R[j];i++) {
C[j] = min(C[j], l[i] + r[i] - H[i]);
}
}
return C;
}
/*
4 2
2 4 3 5
0 2
1 3
*/
