#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const i64 inf = 1e15;
const int N = 1e5 + 1;
int n;
struct SegTree{
struct Info{
i64 dp[21][21];
vector <ar<int,2>> ls, rs;
Info(){
for ( int i = 0; i <= 20; i++ ){
for ( int j = 0; j <= 20; j++ ){
dp[i][j] = inf;
}
}
ls.pb({0, 0});
rs.pb({0, 0});
}
};
vector <Info> T;
void modify(int n){ T.resize(n * 4 + 5); }
void merge(Info &rt, const Info &lf, const Info &rg){
rt = Info();
rt.ls = lf.ls;
for ( auto &[h, v]: rg.ls ){
if ( rt.ls.back()[0] < h ){
rt.ls.pb({h, v});
} else rt.ls.back()[1] += v;
}
rt.rs = rg.rs;
for ( auto &[h, v]: lf.rs ){
if ( rt.rs.back()[0] < h ){
rt.rs.pb({h, v});
} else rt.rs.back()[1] += v;
}
for ( int x = 0; x <= 20; x++ ){
i64 cnt = 0, pf = 0;
for ( auto &[h, v]: rg.ls ){
cnt += h * 1LL * v;
}
int j = 0;
for ( int y = 0; y <= 20; y++ ){
int r = max(y, rg.ls.back()[0]);
cnt += pf;
while ( j < (int)rg.ls.size() && rg.ls[j][0] <= y ){
auto &[h, v] = rg.ls[j++];
cnt += (y - h) * 1LL * v;
pf += v;
}
chmin(rt.dp[x][r], lf.dp[x][y] + cnt);
}
}
for ( int y = 0; y <= 20; y++ ){
i64 cnt = 0, pf = 0;
for ( auto &[h, v]: lf.rs ){
cnt += h * 1LL * v;
}
int j = 0;
for ( int x = 0; x <= 20; x++ ){
int l = max(x, lf.rs.back()[0]);
cnt += pf;
while ( j < (int)lf.rs.size() && lf.rs[j][0] <= x ){
auto &[h, v] = lf.rs[j++];
cnt += (x - h) * 1LL * v;
pf += v;
}
chmin(rt.dp[l][y], rg.dp[x][y] + cnt);
}
}
}
void upd(int v, int l, int r, int p, int x){
if ( l == r ){
T[v].dp[x][x] = x;
T[v].ls.pb({x, 1});
T[v].rs.pb({x, 1});
return;
}
int m = (l + r) / 2;
if ( p <= m ) upd(v * 2, l, m, p, x);
else upd(v * 2 + 1, m + 1, r, p, x);
merge(T[v], T[v * 2], T[v * 2 + 1]);
}
void upd(int p, int x){ upd(1, 0, n - 1, p, x); }
Info get(int v, int l, int r, int tl, int tr){
Info ret;
if ( l > tr or r < tl ) return ret;
if ( tl <= l && tr >= r ){
return T[v];
}
int m = (l + r) / 2;
if ( m < tl ) return get(v * 2 + 1, m + 1, r, tl, tr);
if ( m + 1 > tr ) return get(v * 2, l, m, tl, tr);
merge(ret, get(v * 2, l, m, tl, tr), get(v * 2 + 1, m + 1, r, tl, tr));
return ret;
}
i64 qry(int l, int r){
Info q = get(1, 0, n - 1, l, r);
i64 opt = inf;
for ( int x = 0; x <= 20; x++ ){
for ( int y = 0; y <= 20; y++ ){
chmin(opt, q.dp[x][y]);
}
}
return opt;
};
} seg;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int q = L.size(); n = H.size();
// subtask #4
seg.modify(n);
for ( int i = 0; i < n; i++ ){
seg.upd(i, H[i]);
}
vector <i64> ans(q);
for ( int i = 0; i < q; i++ ){
ans[i] = seg.qry(L[i], R[i]);
}
return ans;
}
