#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
class RangeMinimumQuery {
public:
vector<long long> dat; int size_;
void init(int sz) {
size_ = 1;
while (size_ < sz) size_ *= 2;
dat.resize(size_ * 2, 0LL);
}
void update(int p, long long x) {
p += size_; dat[p] = x;
while (p >= 2) {
p >>= 1;
dat[p] = min(dat[p * 2], dat[p * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (b <= l || r <= a) return (1LL << 60);
long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return min(c1, c2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
class RangeMaximumQuery {
public:
vector<long long> dat; int size_;
void init(int sz) {
size_ = 1;
while (size_ < sz) size_ *= 2;
dat.resize(size_ * 2, 0LL);
}
void update(int p, long long x) {
p += size_; dat[p] = x;
while (p >= 2) {
p >>= 1;
dat[p] = max(dat[p * 2], dat[p * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (b <= l || r <= a) return -(1LL << 60);
long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return max(c1, c2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
long long N, Q, H[5009], T[5009]; pair<int, int> dp[5009][5009];
void dfs(int cl, int cr) {
if (cl > cr) return;
int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
T[cl] += cost * (cr - cm + 1);
T[cm] += cost * (cm - cl);
T[cm + 1] -= cost * (cr - cm);
T[cr + 1] -= cost * (cm - cl + 1);
dfs(cl, cm - 1);
dfs(cm + 1, cr);
}
vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R) {
int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
if(maxh <= 2) {
N = HH.size(); Q = L.size();
for (int i = 0; i < N; i++) H[i] = HH[i];
vector<long long> D2;
for (int i = 0; i < N; i++) { if (H[i] == 2) D2.push_back(i); }
RangeMaximumQuery Z; Z.init(N + 2);
for (int i = 0; i < N; i++) {
if (H[i] == 2) Z.update(i, 0);
else {
int pos1 = lower_bound(D2.begin(), D2.end(), i) - D2.begin();
int pos0 = pos1 - 1;
int cr = N - 1; if (pos1 < D2.size()) cr = D2[pos1] - 1;
int cl = 0; if (pos0 >= 0) cl = D2[pos0] + 1;
Z.update(i, cr - cl + 1);
}
}
vector<long long> ans;
for (int i = 0; i < Q; i++) {
int pos1 = lower_bound(D2.begin(), D2.end(), L[i]) - D2.begin();
int pos2 = lower_bound(D2.begin(), D2.end(), R[i] + 1) - D2.begin();
if (pos1 == pos2) ans.push_back(R[i] - L[i] + 1);
else {
int pl = D2[pos1], pr = D2[pos2 - 1];
long long R1 = Z.query(pl, pr + 1);
long long R2 = (pl - L[i]);
long long R3 = (R[i] - pr);
ans.push_back((2LL * (R[i] - L[i] + 1LL)) - max({R1, R2, R3}));
}
}
return ans;
}
else{
N = HH.size(); Q = L.size();
for (int i = 0; i < N; i++) H[i] = HH[i];
for (int i = 0; i < N; i++) {
pair<int, int> BASE = make_pair(-1, -1);
for (int j = i; j < N; j++) {
BASE = max(BASE, make_pair((int)H[j], j));
dp[i][j] = BASE;
}
}
vector<long long> ans;
for (int i = 0; i < Q; i++) {
for (int j = 0; j <= N; j++) T[j] = 0;
dfs(L[i], R[i]);
for (int j = 1; j <= N; j++) T[j] += T[j - 1];
long long rem = (1LL << 60);
for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
ans.push_back(rem);
}
return ans;
}
}
