#include "meetings.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 750005;
int h[N], l[N], r[N], n, q;
ll ans[N];
int lst[N][22], nxt[N][22];
int lst_geq[N][22], nxt_geq[N][22];
V<pi> G[N];
ll t[N * 4], lz[N * 4];
void apply(int v, ll x) {
t[v] += x;
lz[v] += x;
}
void push(int v) {
apply(v * 2, lz[v]);
apply(v * 2 + 1, lz[v]);
lz[v] = 0;
}
void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
apply(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) upd(l, r, x, v * 2, tl, tm);
if(r > tm) upd(l, r, x, v * 2 + 1, tm, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
ll qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) return t[v];
push(v);
int tm = (tl + tr) / 2;
ll res = 1e18;
if(l < tm) res = min(res, qry(l, r, v * 2, tl, tm));
if(r > tm) res = min(res, qry(l, r, v * 2 + 1, tm, tr));
return res;
}
void solve() {
for(int i = 0; i < q; i++)
G[r[i]].EB(l[i], i);
for(int i = 0; i < n; i++) {
for(int j = 1; j <= 21; j++)
lst[i][j] = i - 1 >= 0 ? lst[i - 1][j] : -1;
lst[i][h[i]] = i;
}
for(int i = n - 1; i >= 0; i--) {
for(int j = 1; j <= 21; j++)
nxt[i][j] = i + 1 < n ? nxt[i + 1][j] : n;
nxt[i][h[i]] = i;
}
for(int i = 0; i < n; i++) {
for(int j = 21; j >= 1; j--) {
lst_geq[i][j] = lst[i][j];
if(j + 1 <= 21) lst_geq[i][j] = max(lst_geq[i][j], lst_geq[i][j + 1]);
nxt_geq[i][j] = nxt[i][j];
if(j + 1 <= 21) nxt_geq[i][j] = min(nxt_geq[i][j], nxt_geq[i][j + 1]);
}
}
for(int i = 0; i < n; i++) {
for(int j = 1; j <= 20; j++) {
if(nxt[i][j] < n) {
int lb = max(nxt[i][j], i + 1), rb = nxt_geq[i][j + 1] - 1;
if(lb > rb) continue;
upd(lb, rb + 1, j);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 1; j <= 20; j++)
if(lst[i][j] >= 0) {
int rb = lst[i][j], lb = lst_geq[i][j + 1] + 1;
if(lb > rb) continue;
upd(lb, rb + 1, j);
}
for(auto[j, qi]:G[i]) {
V<array<int, 3>> todo;
if(j) {
for(int k = 1; k <= 20; k++) {
int rb = lst[j - 1][k], lb = lst_geq[j - 1][k + 1] + 1;
int small = j - 1 - rb, same = max(rb - lb + 1, 0);
int lbb = nxt[j][k], rbb = nxt_geq[j][k + 1] - 1;
if(j < nxt_geq[j][k]) todo.PB({j, nxt_geq[j][k], same * k});
if(lbb <= rbb) todo.PB({lbb, rbb + 1, (small + same) * k});
}
}
for(auto[lb, rb, x]:todo)
upd(lb, rb, -x);
ans[qi] = qry(j, i + 1);
for(auto[lb, rb, x]:todo)
upd(lb, rb, x);
}
}
}
V<ll> minimum_costs(vi _h, vi _l, vi _r) {
n = SZ(_h), q = SZ(_l);
for(int i = 0; i < n; i++) h[i] = _h[i];
for(int i = 0; i < q; i++) l[i] = _l[i], r[i] = _r[i];
solve();
V<ll> tt;
for(int i = 0; i < q; i++)
tt.PB(ans[i]);
return tt;
}
