#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
const int N = 21;
struct node {
int mx=0;
int cl[N], cr[N];
int lmx[N], rmx[N];
node() {
for(int i=0;i<N;++i) lmx[i]=oo,rmx[i]=oo;
for(int i=0;i<N;++i) {
cl[i]=cr[i]=0;
}
}
node(int v) {
*this=node();
mx=v;
lmx[v]=v;
rmx[v]=v;
for(int i=0;i<N;++i) {
cl[i]=max(v,i);
cr[i]=max(v,i);
}
}
void merge(const node& o) {
array<int,N> resl, resr;
fill(all(resl),oo), fill(all(resr),oo);
auto take = [&](int l, int val, int r) {
if(val>=oo) return;
if(l>r) {
resl[r]=min(resl[r],val);
} else resr[l]=min(resr[l],val);
};
for(int i=0;i<=max(mx,o.mx);++i) {
take(mx, lmx[i] + o.cl[i], max(o.mx,i));
take(i, rmx[i] + o.cl[mx], max(o.mx,mx));
take(max(mx,i), cr[i] + o.rmx[i], o.mx);
take(max(mx,o.mx), cr[o.mx] + o.lmx[i], i);
}
for(int i=0;i<N;++i) {
cl[i] += o.cl[max(i,mx)];
cr[i] = cr[max(i,o.mx)] + o.cr[i];
}
copy(all(resl),lmx);
copy(all(resr),rmx);
mx=max(mx,o.mx);
}
friend node merge(node a, const node& b) {
a.merge(b);
return a;
}
};
struct segtree {
vector<node> s;
int ptwo=1;
segtree(int n) {
while(ptwo<n) ptwo*=2;
s.resize(ptwo*2,{});
}
void build() {
for(int i=ptwo-1;i>=1;--i) {
s[i] = merge(s[i*2],s[i*2+1]);
}
}
node query(int l, int r) { // [l,r]
l+=ptwo,r+=ptwo;
node resl, resr;
while(l<=r) {
if(l%2==1) {
resl.merge(s[l]);
l++;
}
if(r%2==0) {
resr = merge(s[r],resr);
r--;
}
l/=2;
r/=2;
}
return merge(resl,resr);
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int mx = *max_element(all(H));
assert(mx<=20);
int n = H.size();
segtree seg(n);
for(int i=0;i<n;++i) {
seg.s[seg.ptwo+i]=H[i];
}
seg.build();
std::vector<long long> C;
for(int i=0;i<Q;++i) {
int l= L[i],r = R[i];
auto res = seg.query(l,r);
int ans = oo;
for(int i=0;i<N;++i) {
ans=min(ans,res.lmx[i]);
ans=min(ans,res.rmx[i]);
}
C.push_back(ans);
}
return C;
}
