#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll solve(int n, vector<int> H){
vector<ll> ans(n);
ll v = 0;
stack<pair<ll, int>> st;
for(int i = 0; i < n; i++){
int j = i;
while(!st.empty() && st.top().first < H[i]){
v -= st.top().first * st.top().second;
j -= st.top().second;
st.pop();
}
v += ll(H[i])*(i-j);
ans[i] += v;
v += H[i];
if(!st.empty() && st.top().first == H[i]) st.top().second += i+1-j;
else st.emplace(H[i], i+1-j);
}
v = 0;
st = stack<pair<ll, int>>();
for(int i = n-1; i >= 0; i--){
ans[i] += v;
int j = i;
while(!st.empty() && st.top().first < H[i]){
v -= st.top().first * st.top().second;
j += st.top().second;
st.pop();
}
v += ll(H[i])*(j+1-i);
if(!st.empty() && st.top().first == H[i]) st.top().second += j+1-i;
else st.emplace(H[i], j+1-i);
}
ll mi = INF;
for(int i = 0; i < n; i++) mi = min(mi, ans[i]+H[i]);
return mi;
}
struct Data{
int pref, suff, ans, all;
Data(int x=0):pref(x),suff(x),ans(x),all(x){}
};
Data combine(Data a, Data b){
Data c;
c.ans = max(a.ans, b.ans);
c.ans = max(c.ans, a.suff+b.pref);
if(a.all) c.pref = a.pref+b.pref;
else c.pref = a.pref;
if(b.all) c.suff = a.suff+b.suff;
else c.suff = b.suff;
c.all = a.all&b.all;
return c;
}
int cap;
vector<Data> seg;
void init(vector<int> h){
int n = int(h.size());
for(cap=1; cap < n; cap*=2);
seg.resize(2*cap);
for(int i = 0; i < n; i++) seg[i+cap] = Data(2-h[i]);
for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
}
Data qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return seg[i];
if(b < l || r < a) return Data(0);
int m = (a+b)/2;
return combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}
Data qry(int l, int r){return qry(l, r, 1, cap, 1);}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = (int)L.size();
vector<ll> C(Q);
int maxH = *max_element(H.begin(), H.end());
if(maxH > 2){
for(int j = 0; j < Q; ++j){
vector<int> h;
for(int k = L[j]; k <= R[j]; k++) h.push_back(H[k]);
C[j] = solve((int)h.size(), h);
}
}
else{
init(H);
for(int i = 0; i < Q; i++){
C[i] = 2*(R[i]-L[i]+1) - qry(L[i]+1, R[i]+1).ans;
}
}
return C;
}
