//
// Created by 42kangaroo on 25/08/2024.
//
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
struct No {
int l, r;
ll miIn;
};
struct Node {
No data;
int l, r, hi, ind;
};
No comb(No l, int mi, No r) {
if (l.miIn == -1) return r;
if (r.miIn == -1) return l;
if (l.l > r.l) swap(l, r);
return {l.l, r.r, min((l.r - l.l + 1)*mi + r.miIn, (r.r - l.r + 1)*mi + l.miIn)};
}
int construct(int l, int r, int h, vector<int>& ve, vector<Node>& out) {
if (l == r) return 0;
vector<int> inds;
for (int i = l; i < r; ++i) {
if (ve[i] == h) inds.push_back(i);
}
if (inds.empty()) return construct(l, r, h - 1, ve, out);
int ind = out.size();
out.push_back({{}, -1, -1, h, inds[inds.size()/2]});
out[ind].l = construct(l, inds[inds.size()/2], h, ve, out);
out[ind].r = construct(inds[inds.size()/2] + 1, r, h, ve, out);
out[ind].data = comb(out[out[ind].l].data, h, out[out[ind].r].data);
return ind;
}
No query(int l, int r, int i, vector<Node>& nos) {
if (r <= nos[i].l || nos[i].r <= l) return nos[0].data;
if (l <= nos[i].l && nos[i].r < r) return nos[i].data;
if (l > nos[i].ind) return query(l, r, nos[i].r, nos);
if (r <= nos[i].ind) return query(l, r, nos[i].l, nos);
return comb(query(l, r, nos[i].l, nos), nos[i].hi, query(l, r, nos[i].r, nos));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
vector<Node> nos{{-1, -1, -1}};
construct(0, H.size(), 20, H, nos);
vector<ll> res(L.size());
for (int i = 0; i < L.size(); ++i) {
res[i] = query(L[i], R[i] + 1, 1, nos).miIn;
}
return res;
}
