#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 2, SQR = 2000;
int nxtL[N], nxtR[N];
vector <int> height;
int cost(int l, int r, int u) {
int ans = 0;
for (int i = u; i >= l;) {
int k = max(l, nxtL[i] + 1);
ans += height[i] * (i - k + 1);
i = k - 1;
}
for (int i = u; i <= r;) {
int k = min(r, nxtR[i] - 1);
ans += height[i] * (k - i + 1);
i = k + 1;
}
return ans -= height[u];
}
int cache[SQR + 1][N];
int dnc(int l, int r) {
if (l > r) return 1e9;
if (l == r) return height[l];
if (r - l <= SQR && cache[r - l][l])
return cache[r - l][l];
int mid = (l + r) >> 1; int ans = 2e9;
vector <int> le, ri;
for (int i = mid; i >= l; i = nxtL[i]) le.emplace_back(i);
reverse(le.begin(), le.end());
for (int i = mid + 1; i <= r; i = nxtR[i]) ri.emplace_back(i);
int id = ri.size() - 1, sumL = 0, sumR = 0;
for (int pos: le) {
int k = max(nxtL[pos] + 1, l); // k -> pos
if (l < k) {
int B = nxtL[pos];
int A = max(nxtL[B] + 1, l);
sumL += (B - A + 1) * height[B];
}
int R = min(r + 1, nxtR[pos]);
while (id >= 0 && ri[id] >= R) {
if (id == ri.size() - 1) sumR += (r - ri[id] + 1) * height[ri[id]];
else sumR += (ri[id + 1] - ri[id]) * height[ri[id]];
--id;
}
int costL = sumL + dnc(k, pos) + height[pos] * (mid - pos);
int costR = height[pos] * (R - 1 - mid) + sumR;
ans = min(ans, costL + costR);
}
reverse(ri.begin(), ri.end());
id = sumL = sumR = 0;
for (int pos: ri) {
int k = min(nxtR[pos] - 1, r);
if (k < r) {
int A = nxtR[pos];
int B = min(nxtR[A] - 1, r);
sumR += (B - A + 1) * height[A];
}
int L = max(nxtL[pos], l - 1);
while (id < le.size() && le[id] <= L) {
if (id == 0) sumL += (le[id] - l + 1) * height[le[id]];
else sumL += (le[id] - le[id - 1]) * height[le[id]];
++id;
}
int costL = sumL + height[pos] * (mid - L);
int costR = (pos - 1 - mid) * height[pos] + dnc(pos, k) + sumR;
ans = min(ans, costL + costR);
}
if (r - l <= SQR) cache[r - l][l] = ans;
return ans;
}
vector <ll> minimum_costs(vector <int> H, vector <int> L, vector <int> R) {
assert (*max_element(H.begin(), H.end()) <= 20);
height = H; int n = H.size(); stack <int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
nxtL[i] = (st.empty() ? -1 : st.top()); st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
nxtR[i] = (st.empty() ? n : st.top()); st.emplace(i);
}
vector <ll> ans;
for (int i = 0; i < L.size(); i++)
ans.emplace_back(dnc(L[i], R[i]));
return ans;
}
