#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], le[21], ri[21];
int mx;
Info(){
for ( int i = 0; i <= 20; i++ ){
for ( int j = 0; j <= 20; j++ ){
dp[i][j] = inf;
}
}
for ( int h = 0; h <= 20; h++ ){
le[h] = ri[h] = inf;
} mx = -1;
}
};
vector <Info> T;
void modify(int n){ T.resize(n * 3 + 5); }
void merge(Info &rt, const Info &lf, const Info &rg){
rt = Info();
for ( int x = 0; x <= 20; x++ ){
for ( int y = 0; y <= 20; y++ ){
chmin(rt.dp[x][max(rg.mx, y)], lf.dp[x][y] + rg.le[y]);
chmin(rt.dp[max(x, lf.mx)][y], rg.dp[x][y] + lf.ri[x]);
}
}
for ( int h = 0; h <= 20; h++ ){
rt.le[h] = lf.le[h] + rg.le[max(lf.mx, h)];
rt.ri[h] = rg.ri[h] + lf.ri[max(rg.mx, h)];
}
rt.mx = max(lf.mx, rg.mx);
}
void upd(int v, int l, int r, int p, int x){
if ( l == r ){
T[v].dp[x][x] = x;
T[v].mx = x;
for ( int h = 0; h <= 20; h++ ){
T[v].le[h] = max(h, x);
T[v].ri[h] = max(h, x);
}
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;
}
