//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "meetings.h"
const int maxn = 1e5+10;
ll hmm[22][22];
struct node{
vector <pair<pii,ll> > f;
pair<ll,int> pre[21],suf[21];
ll mn;
} tree[maxn*4];
int h[maxn];
int n;
node merge(node a,node b) {
node ret;
rep(i,1,21) {
ret.pre[i] = {a.pre[i].fi + b.pre[a.pre[i].se].fi, b.pre[a.pre[i].se].se};
ret.suf[i] = {b.suf[i].fi + a.suf[b.suf[i].se].fi, a.suf[b.suf[i].se].se};
}
//left
for (auto it:a.f) {
int l = it.fi.fi;
int r = b.pre[it.fi.se].se;
if (hmm[l][r] == -1) ret.f.pb({{l,r},0}),hmm[l][r] = it.se + b.pre[it.fi.se].fi;
else hmm[l][r] = min(hmm[l][r],it.se + b.pre[it.fi.se].fi);
}
//right
for (auto it:b.f) {
int r = it.fi.se;
int l = a.suf[it.fi.fi].se;
if (hmm[l][r] == -1) ret.f.pb({{l,r},0}),hmm[l][r] = it.se + a.suf[it.fi.fi].fi;
else hmm[l][r] = min(hmm[l][r],it.se + a.suf[it.fi.fi].fi);
}
ret.mn = 1e18;
rep(i,0,SZ(ret.f)) ret.f[i].se = hmm[ret.f[i].fi.fi][ret.f[i].fi.se], hmm[ret.f[i].fi.fi][ret.f[i].fi.se] = -1,ret.mn = min(ret.mn,ret.f[i].se);
return ret;
}
void init(int c,int cl,int cr) {
if (cl==cr) {
rep(i,1,21) tree[c].pre[i] = tree[c].suf[i] = {max(i,h[cl]),max(i,h[cl])};
tree[c].f.pb({{h[cl],h[cl]},h[cl]});
tree[c].mn = h[cl];
return;
}
int mid=cl+cr>>1;
init(c<<1,cl,mid);
init(c<<1|1,mid+1,cr);
tree[c] = merge(tree[c<<1],tree[c<<1|1]);
assert(!tree[c].f.empty());
}
node query(int c,int cl,int cr,int l,int r) {
if (l<=cl and cr<=r) return tree[c];
int mid=cl+cr>>1;
if (l<=mid and r<=mid) return query(c<<1,cl,mid,l,r);
if (r>mid and l>mid) return query(c<<1|1,mid+1,cr,l,r);
return merge(query(c<<1,cl,mid,l,r),query(c<<1|1,mid+1,cr,l,r));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
memset(hmm,-1,sizeof(hmm));
std::vector<long long> C;
n = SZ(H);
rep(i,0,n) h[i] = H[i];
init(1,0,n-1);
rep(i,0,SZ(L)) {
ll tmp = query(1,0,n-1,L[i],R[i]).mn;
C.pb(tmp);
}
return C;
}
