#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define X first
#define Y second
using namespace std;
ll ez(int l, int r, vector<int>& H){
vector<ll> le, ri, st, am;
le.assign(H.size(), 0);
ri.assign(H.size(), 0);
ll cur = 0;
for(int i = l; i<=r; i++){
ll tmp = 1;
while(st.size()>0 && st.back() <= H[i]){
tmp+=am.back();
cur-=am.back()*st.back();
st.pop_back();
am.pop_back();
}
cur+=tmp*H[i];
le[i] = cur;
st.pb((ll)H[i]);
am.pb(tmp);
}
cur = 0;
st.clear(); am.clear();
for(int i = r; i>=l; i--){
ll tmp = 1;
while(st.size()>0 && st.back() <= H[i]){
tmp+=am.back();
cur-=am.back()*st.back();
st.pop_back();
am.pop_back();
}
cur+=tmp*H[i];
ri[i] = cur;
st.pb((ll)H[i]);
am.pb(tmp);
}
ll ret = 1e15;
for(int i = l; i<=r; i++){
ret = min(ret, le[i]+ri[i]-H[i]);
}
return ret;
}
struct node{
int prf, suf, sum, flag;
};
vector<node> seg;
node conq(node& a, node& b){
node c;
c.flag = a.flag & b.flag;
if(a.flag){
c.prf = a.sum + b.prf;
}else{
c.prf = a.prf;
}
if(b.flag){
c.suf = a.suf + b.sum;
}else{
c.suf = b.suf;
}
c.sum = max(a.sum, b.sum);
c.sum = max(c.sum, a.suf + b. prf);
return c;
}
void build(int v, int tl, int tr, vector<int>& H){
if(tl == tr){
if(H[tl] == 1){
seg[v] = {1, 1, 1, 1};
}
return;
}
int tm = (tl+tr)/2;
build(v*2, tl, tm, H);
build(v*2+1, tm+1, tr, H);
seg[v] = conq(seg[2*v], seg[2*v+1]);
}
node qer(int v, int tl, int tr, int l, int r){
if(tl > r || tr < l)return {-1, -1, -1, -1};
if(tl >= l && tr <= r)return seg[v];
int tm = (tl+tr)/2;
node le = qer(v*2, tl, tm, l, r);
node ri = qer(v*2+1, tm+1, tr, l, r);
if(le.flag == -1)return ri;
if(ri.flag == -1)return le;
return conq(le, ri);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
int N = H.size();
vector<ll> C(Q);
if(N <= 5005 && Q <= 5005){
for (int j = 0; j < Q; ++j) {
C[j] = ez(L[j], R[j], H);
}
return C;
}
seg.assign(4*N, {0, 0, 0, 0});
build(1, 0, N-1, H);
for (int j = 0; j < Q; ++j) {
int sum = qer(1, 0, N-1, L[j], R[j]).sum;
sum+=(R[j]-L[j]+1-sum)*2;
C[j] = sum;
}
return C;
}
