//
// 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.l - 1, r.r, r.miIn + mi};
if (r.miIn == -1) return {l.l, l.r + 1, l.miIn + mi};
return {l.l, r.r, min((ll) (l.r - l.l + 1) * mi + r.miIn, (ll) (r.r - r.l + 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]});
if (l + 1 == r) out.back().data = {l, r, h};
else {
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 (i == 0 || (r <= nos[i].data.l || nos[i].data.r <= l)) return nos[0].data;
if (l <= nos[i].data.l && nos[i].data.r <= r) return nos[i].data;
if ((l == nos[i].ind && l + 1 == min(r, nos[i].data.r)) ||
(r - 1 == nos[i].ind && max(l, nos[i].data.l) + 1 == r))
return {nos[i].ind, nos[i].ind + 1, nos[i].hi};
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;
}
struct Val {
int in, le, ri, tot;
};
Val operator+(const Val &l, const Val &r) {
Val re{max(l.in, max(r.in, r.le + l.ri)), l.le, r.ri, l.tot + r.tot};
if (l.in == l.tot) re.le = l.tot + r.le;
if (r.in == r.tot) re.ri = r.tot + l.ri;
return re;
}
struct SegTe {
vector<Val> a;
Val build(int l, int r, int i, vector<int> &in) {
if (l + 1 == r) return a[i] = {-in[l] + 2, -in[l] + 2, -in[l] + 2, 1};
int m = (l + r) / 2;
return a[i] = build(l, m, 2 * i + 1, in) + build(m, r, 2 * i + 2, in);
}
Val get(int l, int r, int i, int lq, int rq) {
if (rq <= l || r <= lq) return {0, 0, 0, 0};
if (lq <= l && r <= rq) return a[i];
int m = (l + r) / 2;
return get(l, m, 2 * i + 1, lq, rq) + get(m, r, 2 * i + 2, lq, rq);
}
};
std::vector<long long> minimum_costs2(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
SegTe se{vector<Val>(4 * H.size())};
se.build(0, H.size(), 0, H);
vector<long long> res(L.size());
for (int i = 0; i < L.size(); ++i) {
Val re = se.get(0, H.size(), 0, L[i], R[i] + 1);
res[i] = re.tot * 2 - re.in;
}
return res;
}
