#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int DIM = 750005;
const long long INF = 1e18;
int n;
int val[DIM];
struct Line {
long long a, b;
Line(long long _a = 0, long long _b = 0) {a = _a; b = _b;}
long long get(int t) {
return 1LL * a * t + b;
}
};
struct SegTree {
long long lazy[4 * DIM];
Line line[4 * DIM];
void build(int st = 1, int dr = n, int nod = 1) {
lazy[nod] = 0; line[nod] = {0, INF};
if (st == dr) {line[nod] = {0, 0}; return ;}
build(st, (st + dr) / 2, nod * 2);
build((st + dr) / 2 + 1, dr, nod * 2 + 1);
}
void upd(int nod, int val) {
lazy[nod] += val;
line[nod].b += val;
}
void propag(int nod) {
if (lazy[nod] == 0) return ;
for (int i = nod * 2; i <= nod * 2 + 1 ; ++i) upd(i, lazy[nod]);
lazy[nod] = 0;
}
long long query(int x, int st = 1, int dr = n, int nod = 1) {
if (st == dr) return line[nod].get(x);
propag(nod);
int mij = (st + dr) / 2;
if (x <= mij) return min(line[nod].get(x), query(x, st, mij, nod * 2));
return min(line[nod].get(x), query(x, mij + 1, dr, nod * 2 + 1));
}
void update(int x, int y, long long val, int st = 1, int dr = n, int nod = 1) {
if (x <= st && dr <= y) {upd(nod, val); return ;}
propag(nod);
int mij = (st + dr) / 2;
if (x <= mij) update(x, y, val, st, mij, nod * 2);
if (mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
}
void idk(int l, int r, Line newLine, int st = 1, int dr = n, int nod = 1) {
if (l <= st && dr <= r) {
long long A = newLine.get(st), B = line[nod].get(st), C = newLine.get(dr), D = line[nod].get(dr);
if (A <= B && C <= D) {line[nod] = newLine; return ;}
if (A >= B && C >= D) return ;
propag(nod);
int mij = (st + dr) / 2;
if (A <= B) swap(line[nod], newLine);
if (line[nod].get(mij) <= newLine.get(mij)) idk(l, r, newLine, mij + 1, dr, nod * 2 + 1);
else swap(line[nod], newLine), idk(l, r, newLine, st, mij, nod * 2);
return ;
}
propag(nod);
int mij = (st + dr) / 2;
if (l <= mij) idk(l, r, newLine, st, mij, nod * 2);
if (mij + 1 <= r) idk(l, r, newLine, mij + 1, dr, nod * 2 + 1);
}
void merge(int l, int split, int r, int tip) {
if (tip == 0) {
long long aux = query(split - 1);
Line newLine = {val[split], aux - 1LL * (split - 1) * val[split]};
idk(split, r, newLine);
} else {
long long aux = query(split + 1);
Line newLine = {-val[split], aux + 1LL * (split + 1) * val[split]};
idk(l, split, newLine);
}
}
};
SegTree L, R;
struct query {
int l, r, ind;
};
vector <long long> ans;
vector <query> myQ[DIM];
pair <int, int> arb[4 * DIM];
pair <int, int> max(pair <int, int> a, pair <int, int> b) {
if (a.first > b.first || (a.first == b.first && a.second < b.second)) return a;
return b;
}
void build_max(int st = 1, int dr = n, int nod = 1) {
if (st == dr) {arb[nod] = {val[st], st}; return ;}
int mij = (st + dr) / 2;
build_max(st, mij, nod * 2);
build_max(mij + 1, dr, nod * 2 + 1);
arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}
pair <int, int> _get_max(int x, int y, int st = 1, int dr = n, int nod = 1) {
if (x <= st && dr <= y) return arb[nod];
pair <int, int> ans = {-1, -1}; int mij = (st + dr) / 2;
if (x <= mij) ans = max(ans, _get_max(x, y, st, mij, nod * 2));
if (mij + 1 <= y) ans = max(ans, _get_max(x, y, mij + 1, dr, nod * 2 + 1));
return ans;
}
int get_max(int x, int y) {
return _get_max(x, y).second;
}
void solve(int l, int r) {
if (l > r) return ;
int split = get_max(l, r);
solve(l, split - 1);
solve(split + 1, r);
for (auto it : myQ[split])
ans[it.ind] = min(L.query(it.r) + 1LL * (split - it.l + 1) * val[split], R.query(it.l) + 1LL * (it.r - split + 1) * val[split]);
L.update(split, r, 1LL * val[split] * (split - l + 1));
if (split != l) L.merge(l, split, r, 0);
R.update(l, split, 1LL * val[split] * (r - split + 1));
if (split != r) R.merge(l, split, r, 1);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> LQ,
std::vector<int> RQ) {
n = (int)H.size();
for (int i = 1; i <= n ; ++i) val[i] = H[i - 1];
build_max();
int Q = (int)LQ.size();
ans.resize(Q);
for (int i = 0; i < Q ; ++i) myQ[get_max(LQ[i] + 1, RQ[i] + 1)].push_back({LQ[i] + 1, RQ[i] + 1, i});
L.build(); R.build();
solve(1, n);
return ans;
}
