#include "meetings.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
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;
}
int maxH = 20;
struct Data{
int mi;
vector<pair<int, int>> pref, suff;
vector<int> le, ri;
bool id;
Data(int x=-1){
if(x == -1) id = true;
else{
id = false;
pref.emplace_back(x, 1);
suff.emplace_back(x, 1);
le.assign(maxH, 0);
ri.assign(maxH, 0);
le[x] = ri[x] = x;
mi = x;
}
}
};
Data combine(Data a, Data b){
if(a.id) return b;
if(b.id) return a;
Data c;
c.id = false;
int i = sz(b.pref)-1, dis = 0;
for(auto [h, d] : b.pref) dis += d;
int add = 0;
vector<int> toAdd(maxH);
for(int j = 0; j < maxH; j++){
while(i >= 0 && b.pref[i].first <= j){
add += b.pref[i].first*b.pref[i].second;
dis -= b.pref[i].second;
i--;
}
toAdd[j] = add + dis*j;
}
for(int j = 0; j < maxH; j++) a.ri[j] += toAdd[j];
for(int j = 0; j < maxH; j++) a.le[j] += toAdd[a.mi];
i = sz(a.suff)-1, dis = 0;
for(auto [h, d] : a.suff) dis += d;
add = 0;
toAdd.assign(maxH, 0);
for(int j = 0; j < maxH; j++){
while(i >= 0 && a.suff[i].first <= j){
add += a.suff[i].first*a.suff[i].second;
dis -= a.suff[i].second;
i--;
}
toAdd[j] = add + dis*j;
}
for(int j = 0; j < maxH; j++) b.le[j] += toAdd[j];
for(int j = 0; j < maxH; j++) b.ri[j] += toAdd[b.mi];
c.le = a.le;
c.ri = b.ri;
c.mi = min(a.mi, b.mi);
for(int j = 0; j < maxH; j++){
c.le[min(j, a.mi)] = max(c.le[min(j, a.mi)], b.le[j]);
}
for(int j = 0; j < maxH; j++){
c.ri[min(j, b.mi)] = max(c.ri[min(j, b.mi)], a.ri[j]);
}
c.pref = a.pref;
for(i = 0; i < sz(b.pref); i++){
if(b.pref[i].first >= c.pref.back().first) c.pref.back().second += b.pref[i].second;
else c.pref.push_back(b.pref[i]);
}
c.suff = b.suff;
for(i = 0; i < sz(a.suff); i++){
if(a.suff[i].first > c.suff.back().first) c.suff.back().second += a.suff[i].second;
else c.suff.push_back(a.suff[i]);
}
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(maxH-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(b < l || r < a) return Data(-1);
// int ans = max(*max_element(seg[i].le.begin(), seg[i].le.end()), *max_element(seg[i].ri.begin(), seg[i].ri.end()));
// cerr << a << " " << b << " " << ans << "\n";
if(l <= a && b <= r) return seg[i];
int m = (a+b)/2;
Data d = combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
return d;
}
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);
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++){
Data d = qry(L[i]+1, R[i]+1);
int ans = max(*max_element(d.le.begin(), d.le.end()), *max_element(d.ri.begin(), d.ri.end()));
C[i] = maxH*(R[i]-L[i]+1) - ans;
}
}
return C;
}
