#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
using ll = long long;
void chmin(int &x, int v) {
if (x > v) x = v;
}
const int MAX_H = 21;
const int INF = 1e9;
struct Node {
int cost[MAX_H][MAX_H];
int pref[MAX_H], suff[MAX_H];
int maxh;
bool neutr;
Node(int v = 0) {
neutr = true;
for (int h1 = 0; h1 < MAX_H; h1++) {
for (int h2 = 0; h2 < MAX_H; h2++) {
cost[h1][h2] = INF;
}
}
for (int h = 0; h < MAX_H; h++) {
pref[h] = suff[h] = INF;
}
if (v != 0) {
neutr = false;
cost[v][v] = maxh = v;
for (int h = 0; h < MAX_H; h++) {
pref[h] = suff[h] = max(h, v);
}
}
}
int best() {
int ans = INF;
for (int h1 = 0; h1 < MAX_H; h1++) {
for (int h2 = 0; h2 < MAX_H; h2++) {
chmin(ans, cost[h1][h2]);
}
}
return ans;
}
friend Node op(const Node &a, const Node &b) {
if (a.neutr) return b;
if (b.neutr) return a;
Node c;
for (int h1 = 0; h1 < MAX_H; h1++) {
for (int h2 = 0; h2 < MAX_H; h2++) {
chmin(c.cost[h1][max(h2, b.maxh)], a.cost[h1][h2] + b.pref[h2]);
chmin(c.cost[max(h1, a.maxh)][h2], a.suff[h1] + b.cost[h1][h2]);
}
}
for (int h = 0; h < MAX_H; h++) {
c.suff[h] = a.suff[max(h, b.maxh)] + b.suff[h];
c.pref[h] = a.pref[h] + b.pref[max(h, a.maxh)];
}
c.maxh = max(a.maxh, b.maxh);
c.neutr = false;
return c;
}
};
const int SZ = 1 << 17;
Node st[2 * SZ];
void init(vector<int> &H) {
for (int i = 0; i < sz(H); i++) {
st[i + SZ] = H[i];
}
for (int i = SZ - 1; i > 0; i--) {
st[i] = op(st[2 * i], st[2 * i + 1]);
}
}
Node query(int l, int r) {
l += SZ, r += SZ;
Node leftRes, rightRes;
while (l <= r) {
if (l % 2 == 1) leftRes = op(leftRes, st[l++]);
if (r % 2 == 0) rightRes = op(st[r--], rightRes);
l /= 2, r /= 2;
}
return op(leftRes, rightRes);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
init(H);
int Q = sz(L);
vector<ll> ans(Q, INF);
for (int i = 0; i < Q; i++) {
Node res = query(L[i], R[i]);
ans[i] = res.best();
}
return ans;
}
