#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SegTree{
int n;
vector<int> lzy;
vector<ll> sm;
SegTree(int sz) : n(sz), lzy(4*sz, -1), sm(4*sz, 0) {};
void prop(int i, int l, int r) {
if (lzy[i] == -1) return;
sm[i] = 1ll * (r - l) * lzy[i];
if (r - l <= 1) return;
lzy[i * 2 + 1] = lzy[i * 2 + 2] = lzy[i];
lzy[i] = -1;
}
void set(int i, int l, int r, int a, int b, int val) {
prop(i, l, r);
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
lzy[i] = val;
prop(i, l, r);
return;
}
int m = (l+r)>>1;
set(i * 2 + 1, l, m, a, b, val);
set(i * 2 + 2, m, r, a, b, val);
sm[i] = sm[i * 2 + 1] + sm[i * 2 + 2];
}
void set(int a, int b, int val) { set(0, 0, n, a, b, val); }
void clear() { set(0, n, 0); }
ll que(int i, int l, int r, int a, int b) {
prop(i, l, r);
if (b <= l || r <= a) return 0;
if (a <= l && r <= b) return sm[i];
int m = (l+r)>>1;
return que(i * 2 + 1, l, m, a, b) + que(i * 2 + 2, m, r, a, b);
}
ll que(int a, int b) { return que(0, 0, n, a, b); }
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int N = H.size();
int Q = L.size();
std::vector<long long> C(Q);
SegTree st(N);
for (int j = 0; j < Q; ++j) {
int d = R[j] - L[j] + 1;
vector<ll> pref(d), suf(d);
vector<pair<int, int>> stk; stk.push_back({1<<30, L[j]-1});
st.clear();
for (int i = 0; i < d; i++) {
const int x = L[j] + i;
while (stk.back().first <= H[x]) stk.pop_back();
st.set(stk.back().second+1, x + 1, H[x]);
pref[i] = st.que(0, x+1);
stk.push_back({H[x], x});
}
st.clear();
stk.clear(); stk.push_back({1<<30, R[j]+1});
for (int i = d-1; ~i; i--) {
const int x = L[j] + i;
while (stk.back().first <= H[x]) stk.pop_back();
st.set(x, stk.back().second, H[x]);
suf[i] = st.que(x, N);
stk.push_back({H[x], x});
}
ll mn = 1ll<<62;
for (int i = 0; i < d; i++)
mn = min(mn, pref[i] + (i < d - 1 ? suf[i+1] : 0));
C[j] = mn;
}
return C;
}
