#include "meetings.h"
#include <stack>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
const int N = 1e5 + 1, LG = 17 + 1;
long long pre[N], suf[N];
long long mn[LG][N]; // sparse table of mins over pre[x] + suf[x] in range
long long queryMN(int l, int r) {
int i = 0, p2 = 1;
while (p2 <= r-l+1) ++i, p2 <<= 1;
--i, p2 >>= 1;
return min(mn[i][l], mn[i][r-p2+1]);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size(), N = H.size();
vector<long long> C(Q);
if (*max_element(H.begin(), H.end()) <= 20) {
// Convert from zero-based to one-based
H.insert(H.begin(), 0);
for (int &x : L) ++x;
for (int &x : R) ++x;
// Precalculate next and previous of each value from each position
vector<int> nxt[21], prv[21];
for (int i = 0; i <= 20; ++i) {
prv[i] = vector<int>(1+N+1, 0);
nxt[i] = vector<int>(1+N+1, N+1);
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= 20; ++j) prv[j][i] = prv[j][i-1];
prv[H[i]][i] = i;
}
for (int i = N; i >= 1; --i) {
for (int j = 1; j <= 20; ++j) nxt[j][i] = nxt[j][i+1];
nxt[H[i]][i] = i;
}
// Precalculate number with each maximum on each prefix and suffix
vector<int> cntMaxPrefix[21]{}, cntMaxSuffix[21]{};
for (int i = 1; i <= 20; ++i) {
cntMaxPrefix[i].resize(1+N+1);
cntMaxSuffix[i].resize(1+N+1);
}
for (int i = 1; i <= N; ++i) {
cntMaxPrefix[H[i]][i] = 1;
for (int j = 1; j <= H[i]; ++j) cntMaxPrefix[H[i]][i] += cntMaxPrefix[j][i-1];
for (int j = H[i]+1; j <= 20; ++j) cntMaxPrefix[j][i] = cntMaxPrefix[j][i-1];
}
for (int i = N; i >= 1; --i) {
cntMaxSuffix[H[i]][i] = 1;
for (int j = 1; j <= H[i]; ++j) cntMaxSuffix[H[i]][i] += cntMaxSuffix[j][i+1];
for (int j = H[i]+1; j <= 20; ++j) cntMaxSuffix[j][i] = cntMaxSuffix[j][i+1];
}
// Precalculate costs on prefix and suffix
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= 20; ++j) {
pre[i] += cntMaxPrefix[j][i] * j;
suf[i] += cntMaxSuffix[j][i] * j;
}
suf[i] -= H[i]; // prefix includes this value itself, suffix does not
mn[0][i] = pre[i] + suf[i];
}
// Create sparse table for minimums over range
for (int j = 1, p2 = 1; j < LG; ++j, p2 <<= 1) {
for (int i = 1; i <= N; ++i) {
if (i+p2 > N) mn[j][i] = mn[j-1][i];
else mn[j][i] = min(mn[j-1][i], mn[j-1][i+p2]);
}
}
// Answer each query
for (int q = 0; q < Q; ++q) {
int l = L[q], r = R[q];
// Take next of each value from left and previous of each value from right
int soFar = r+1;
vector<pair<int, int>> starts;
for (int j = 20; j >= 1; --j) {
if (nxt[j][l] >= soFar) continue;
soFar = nxt[j][l];
starts.emplace_back(nxt[j][l], j);
}
reverse(starts.begin(), starts.end());
soFar = l-1;
vector<pair<int, int>> ends;
for (int j = 20; j >= 1; --j) {
if (prv[j][r] <= soFar) continue;
soFar = prv[j][r];
ends.emplace_back(prv[j][r], j);
}
vector<pair<int, int>> endsRemade;
for (int start = l, i = 0; i < (int)ends.size(); ++i) {
endsRemade.emplace_back(start, ends[i].second);
start = ends[i].first+1;
}
ends = endsRemade;
vector<pair<int, int>> merged;
for (int i = 0; i < (int)starts.size(); ++i) merged.emplace_back(starts[i].first, starts[i].second);
for (int i = 0; i < (int)ends.size(); ++i) merged.emplace_back(ends[i].first, -ends[i].second);
sort(merged.begin(), merged.end());
C[q] = INF;
for (int i = 0, curL = 0, curR = 0; i < (int)merged.size(); ++i) {
if (merged[i].second > 0) { // Start
curL = merged[i].second;
} else { // End
curR = -merged[i].second;
}
if (i+1 < (int)merged.size() && merged[i+1].first == merged[i].first) continue;
int rangeL = merged[i].first, rangeR = r;
if (i+1 < (int)merged.size()) rangeR = merged[i+1].first-1;
// now calculate best answer in this range
long long best = queryMN(rangeL, rangeR); // min over pre + suf
// subtract before l and after r
for (int j = 1; j <= 20; ++j) {
best -= cntMaxPrefix[j][l-1] * max(j, curL);
best -= cntMaxSuffix[j][r+1] * max(j, curR);
}
C[q] = min(C[q], best);
}
}
} else {
for (int q = 0; q < Q; ++q) {
int l = L[q], r = R[q];
vector<long long> ans(r-l+1);
stack<int> st;
// Find answer contributions from left
st.push(l-1);
long long sum = 0;
for (int i = l; i <= r; ++i) {
while (st.top() >= l && H[st.top()] <= H[i]) {
int x = st.top();
st.pop();
sum += (long long)(x-st.top())*(H[i]-H[x]);
}
st.push(i);
sum += H[i];
ans[i-l] += sum;
}
while (!st.empty()) st.pop();
// Find answer contributions from right
st.push(r+1);
sum = 0;
for (int i = r; i >= l; --i) {
while (st.top() <= r && H[st.top()] <= H[i]) {
int x = st.top();
st.pop();
sum += (long long)(st.top()-x)*(H[i]-H[x]);
}
st.push(i);
sum += H[i];
ans[i-l] += sum;
}
while (!st.empty()) st.pop();
// Choose best answer
long long minCost = INF;
for (int i = l; i <= r; ++i) {
ans[i-l] -= H[i]; // counted from both sides
minCost = min(minCost, ans[i-l]);
}
C[q] = minCost;
}
}
return C;
}
