#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class A,class B>
bool chmin(A &a,B b){
if(a>b){
a=b;
return true;
}
return false;
}
struct S{
int maxh;
vector<int> radd,ladd;
//radd <- 右に max x を付けたときそちらへ移動するときのコストの総和
//ladd <- 左に max x を付けたときそちらへ移動するときのコストの総和
vector<int> rc,lc;
//lc <- (i,maxh) のときのコストの最小値
//rc <- (maxh,i) のときのコストの最小値
S(){
maxh=1;
radd.resize(21);
ladd.resize(21);
lc.resize(21);
rc.resize(21);
}
S(int x){
maxh=x;
radd.resize(21);
ladd.resize(21);
for(int i=0;i<=20;i++){
radd[i]=max(i,x);
ladd[i]=max(i,x);
}
lc.resize(21);
rc.resize(21);
for(int i=0;i<=20;i++){
lc[i]=rc[i]=1000000000;
}
lc[x]=rc[x]=x;
}
};
S op(S a, S b){
S c;
for(int i=1;i<=20;i++){
c.lc[i]=c.rc[i]=1000000000;
}
c.maxh=max(a.maxh,b.maxh);
for(int i=1;i<=20;i++){
c.radd[i]=a.radd[max(i,b.maxh)]+b.radd[i];
c.ladd[i]=a.ladd[i]+b.ladd[max(i,a.maxh)];
}
for(int i=1;i<=20;i++){
//a.lc[i] から
//(i,max(a,b))
chmin(c.lc[i],a.lc[i]+b.ladd[a.maxh]);
//b.rc[i] から
//(max(a,b),i)
chmin(c.rc[i],a.radd[b.maxh]+b.rc[i]);
//a.rc[i] から
//(max a,max(max b,i))
if(a.maxh==c.maxh){
chmin(c.rc[max(b.maxh,i)],a.rc[i]+b.ladd[i]);
}
else{
chmin(c.lc[a.maxh],a.rc[i]+b.ladd[i]);
}
//b.lc[i] から
//(max(max a,i),max b)
if(b.maxh==c.maxh){
chmin(c.lc[max(a.maxh,i)],b.lc[i]+a.radd[i]);
}
else{
chmin(c.rc[b.maxh],b.lc[i]+a.radd[i]);
}
}
return c;
}
S e(){
return S();
}
struct segtree{
int n;
vector<S> node;
segtree(int n_){
n=1;
while(n<n_){
n*=2;
}
node.resize(2*n);
}
void set(int i,S x){
i+=n;
node[i]=x;
while(i/2){
i/=2;
node[i]=op(node[2*i],node[2*i+1]);
}
}
S prod(int l,int r,int a,int b,int k){
if(r<=a||b<=l) return e();
if(l<=a&&b<=r) return node[k];
return op(prod(l,r,a,(a+b)/2,2*k),prod(l,r,(a+b)/2,b,2*k+1));
}
S prod(int l,int r){
return prod(l,r,0,n,1);
}
};
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,std::vector<int> r) {
int n=h.size();
int q=l.size();
vector<ll> ans(q,1ll<<60);
for(int i=0;i<n;i++) assert(h[i]<=20);
segtree seg(n);
for(int i=0;i<n;i++) seg.set(i,S(h[i]));
for(int i=0;i<q;i++){
S v=seg.prod(l[i],r[i]+1);
//cout<<v.maxh<<endl;
for(int j=1;j<=20;j++){
//cout<<v.lc[j]<<" "<<v.rc[j]<<endl;
chmin(ans[i],v.lc[j]);
chmin(ans[i],v.rc[j]);
}
}
return ans;
}
