#include "meetings.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const ll infinity = 1e18;
struct Seg {
int n;
vi seg, add;
Seg () {}
Seg (int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n), add.resize(2 * n);
}
inline void pull(int i) {
seg[i] = min(Val(i << 1), Val(i << 1 | 1));
}
inline void push(int i) {
add[i << 1] += add[i];
add[i << 1 | 1] += add[i];
seg[i] += add[i];
add[i] = 0;
}
inline ll Val(int i) {
return seg[i] + add[i];
}
void update(int a, int b, ll x, int ind, int l, int r) {
if (a <= l && r <= b) {
add[ind] += x;
return;
}
if (r <= a || b <= l) return;
push(ind);
update(a, b, x, ind << 1, l, (l + r) >> 1);
update(a, b, x, ind << 1 | 1,(l + r) >> 1, r);
pull(ind);
}
inline void update(int a, int b, ll x) {
update(a, b, x, 1, 0, n);
}
ll query(int a, int b, int ind, int l, int r) {
if (a <= l && r <= b) return Val(ind);
if (r <= a || b <= l) return infinity;
push(ind);
return min(query(a, b, ind << 1, l, (l + r) >> 1),
query(a, b, ind << 1 | 1,(l + r) >> 1, r));
}
inline ll query(int a, int b) {
return query(a, b, 1, 0, n);
}
};
const int block = 500;
const int MAX_N = 1e5 + 5;
int lefts[MAX_N], rights[MAX_N];
ll h[MAX_N];
int n;
Seg seg;
void Add(int i, int x) {
int v = i;
while (v != -1) {
int nex = lefts[v];
seg.update(nex + 1, v + 1, x * h[v]);
v = nex;
}
v = i;
while (v != n) {
int nex = rights[v];
seg.update(v, nex, x * h[v]);
v = nex;
}
seg.update(i, i + 1, -x * h[i]);
}
vi minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int q = L.size();
n = H.size();
for (int i = 0; i < n; i++) h[i] = H[i];
vi ans(q);
stack<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && h[stk.top()] <= h[i]) stk.pop();
lefts[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
while (!stk.empty()) stk.pop();
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && h[stk.top()] <= h[i]) stk.pop();
rights[i] = stk.empty() ? n : stk.top();
stk.push(i);
}
seg = Seg(n);
int a = 0, b = -1;
vi ind(q);
iota(all(ind), 0);
sort(all(ind), [&] (int i, int j) {
return L[i] / block == L[j] / block ? R[i] < R[j] : L[i] < L[j];
});
for (int j : ind) {
int l = L[j], r = R[j];
while (a < l) {
Add(a++, -1);
}
while (a > l) {
Add(--a, 1);
}
while (b < r) {
Add(++b, 1);
}
while (b > r) {
Add(b--, -1);
}
ans[j] = seg.query(l, r + 1);
}
// left[0] = h[0] == 1 ? -1 : 0;
// for (int i = 1; i < n; i++) {
// left[i] = left[i - 1];
// if (h[i] == 2) left[i] = i;
// }
// right[n - 1] = h[n - 1] == 1 ? n : n - 1;
// for (int i = n - 2; i >= 0; i--) {
// right[i] = right[i + 1];
// if (h[i] == 2) right[i] = i;
// }
// Seg seg(n);
// for (int i = 0; i < n; i++) {
// if (h[i] == 1) {
// seg.update(i, right[i] - left[i] - 1);
// }
// }
// for (int j = 0; j < q; j++) {
// int l = L[j], r = R[j];
// if (h[l] == 1 && right[l] > r) {
// ans[j] = r - l + 1;
// continue;
// }
// int max_len = 0;
// if (h[l] == 1) {
// chkmax(max_len, right[l] - l);
// l = right[l];
// }
// if (h[r] == 1) {
// chkmax(max_len, r - left[r]);
// r = left[r];
// }
// chkmax(max_len, seg.query(l, r));
// ans[j] = 2 * (R[j] - L[j] + 1) - max_len;
// }
return ans;
}
//10 3
//1 2 2 1 1 1 2 1 1 2
//2 5
//3 7
//4 9
