#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, 0), sm(4*sz, 0) {};
void prop(int i, int l, int r) {
if (!lzy[i]) 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] = 0;
}
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); }
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); }
ll que() {return que(0, n); }
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int Q = L.size();
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
int d = R[j] - L[j] + 1;
SegTree a(d), b(d);
vector<ll> pref(d), suf(d);
vector<pair<int, int>> stk; stk.push_back({1<<30, -1});
for (int i = 0; i < d; i++) {
const int x = L[j] + i;
while (stk.back().first <= H[x]) stk.pop_back();
a.set(stk.back().second+1, i + 1, H[x]);
pref[i] = a.que();
stk.push_back({H[x], i});
}
stk.clear(); stk.push_back({1<<30, d});
for (int i = d-1; ~i; i--) {
const int x = L[j] + i;
while (stk.back().first <= H[x]) stk.pop_back();
b.set(i, stk.back().second, H[x]);
suf[i] = b.que();
stk.push_back({H[x], i});
}
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;
}
