#include "meetings.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Node {
int l, r, a, b, tot;
Node operator+(Node B) {
Node ret = {l, B.r, (tot == r - l + 1 ? tot + B.a : a),
(B.tot == B.r - B.l + 1 ? b + B.tot : B.b),
max({tot, B.tot, b + B.a})};
return ret;
}
} segtree[400001];
int n, h[100001];
ll dp[5000];
void build(int node = 1, int l = 0, int r = n - 1) {
if (l == r) segtree[node] = {l, r, h[l] == 1, h[l] == 1, h[l] == 1};
else {
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}
}
Node query(int a, int b, int node = 1, int l = 0, int r = n - 1) {
if (a <= l && b >= r) return segtree[node];
int mid = (l + r) / 2;
if (mid >= a) {
if (mid + 1 <= b) return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
return query(a, b, node * 2, l, mid);
}
return query(a, b, node * 2 + 1, mid + 1, r);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
for (int i = 0; i < n; i++) h[i] = H[i];
int Q = int(L.size());
vector<long long> C(Q);
if (Q <= 5000) {
for (int i = 0; i < Q; i++) {
memset(dp, 0, sizeof dp);
stack<pair<int, ll>> stck;
ll val = 0;
for (int j = L[i]; j <= R[i]; j++) {
while (stck.size() && H[stck.top().first] <= H[j]) {
val -= H[stck.top().first] * stck.top().second;
stck.pop();
}
ll rng = (stck.size() ? j - stck.top().first : j - L[i] + 1);
val += rng * H[j];
dp[j] += val;
stck.push({j, rng});
// cout << dp[j] << ' ';
}
// cout << "| ";
while (stck.size()) stck.pop();
val = 0;
for (int j = R[i]; j >= L[i]; j--) {
while (stck.size() && H[stck.top().first] <= H[j]) {
val -= H[stck.top().first] * stck.top().second;
stck.pop();
}
ll rng = (stck.size() ? stck.top().first - j : R[i] - j + 1);
val += rng * H[j];
dp[j] += val - H[j];
stck.push({j, rng});
// cout << dp[j] << ' ';
}
// cout << '\n';
C[i] = *min_element(dp + L[i], dp + R[i] + 1);
}
} else {
build();
for (int i = 0; i < Q; i++) {
C[i] = 2 * (R[i] - L[i] + 1) - query(L[i], R[i]).tot;
}
}
return C;
}
