#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
const ll INF = 1e18;
void ckmax(int& a, int b){
a = max(a, b);
}
void ckmin(ll& a, ll b){
a = min(a, b);
}
const int MOD = 1e9+7;
const int mx = 100005;
mt19937 rng(127);
int N, Q;
struct Node{
bool is_ID;
array<ll, 21> meet_in_right;
array<ll, 21> meet_in_left;
array<ll, 21> meet_from_left;
array<ll, 21> meet_from_right;
int max_val;
Node(){
}
Node(int val){
if(val == -1){
is_ID = 1;
}
else if(val == -2){ //use for comb
is_ID = 0;
for(int i = 1; i <= 20; i++){
meet_in_right[i] = meet_in_left[i] = INF;
}
}
else{
is_ID = 0;
max_val = val;
for(int i = 1; i <= 20; i++){
meet_in_right[i] = meet_in_left[i] = INF;
}
meet_in_right[val] = meet_in_left[val] = val;
for(int i = 1; i <= 20; i++){
meet_from_left[i] = meet_from_right[i] = max(i, val);
}
}
}
};
void print(Node a){
for(int i = 1; i <= 20; i++){
cout << a.meet_in_right[i] << " " << a.meet_in_left[i] << "\n";
}
}
Node comb(const Node& a, const Node& b){
Node res = Node(-2);
if(a.is_ID){
res = b;
return res;
}
if(b.is_ID){
res = a;
return res;
}
res.max_val = max(a.max_val, b.max_val);
//compute res.meet_in_right
for(int i = 1; i <= 20; i++){
//consider left start
ckmin(res.meet_in_right[max(i, b.max_val)], a.meet_in_right[i]+b.meet_from_left[i]);
//consider right start
ckmin(res.meet_in_right[i], a.meet_from_right[b.max_val]+b.meet_in_right[i]);
ckmin(res.meet_in_right[b.max_val], a.meet_from_right[i]+b.meet_in_left[i]);
}
for(int i = 1; i <= 20; i++){
//consider left start
ckmin(res.meet_in_left[i], a.meet_in_left[i]+b.meet_from_left[a.max_val]);
ckmin(res.meet_in_left[a.max_val], a.meet_in_right[i]+b.meet_from_left[i]);
//consider right start
ckmin(res.meet_in_left[max(a.max_val, i)], a.meet_from_right[i]+b.meet_in_left[i]);
}
for(int i = 1; i <= 20; i++){
res.meet_from_left[i] = a.meet_from_left[i]+b.meet_from_left[max(i, a.max_val)];
res.meet_from_right[i] = a.meet_from_right[max(i, b.max_val)]+b.meet_from_right[i];
}
return res;
}
const int SZ = 131072;
Node seg[2*SZ];
void pull(int ind){
seg[ind] = comb(seg[2*ind], seg[2*ind+1]);
}
void build(){
for(int i = SZ-1; i >= 1; i--){
pull(i);
}
}
Node query(int l, int r, int ind = 1, int L = 0, int R = SZ-1){
if(r < L || R < l) return Node(-1);
if(l <= L && R <= r){
return seg[ind];
}
int M = (L+R)/2;
return comb(query(l, r, 2*ind, L, M), query(l, r, 2*ind+1, M+1, R));
}
vl minimum_costs(vi H, vi L, vi R) {
// cout << "HI" << "\n";
// cout.flush();
N = sz(H);
Q = sz(L);
for(int i = 0; i < N; i++){
seg[SZ+i] = Node(H[i]);
}
build();
// print(seg[SZ+0]);
vl C(Q, INF);
for(int i = 0; i < Q; i++){
Node res = query(L[i], R[i]);
for(int j = 1; j <= 20; j++){
ckmin(C[i], res.meet_in_left[j]);
}
}
return C;
}
