#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e6 + 10;
struct Seg{
ll l, r, lazy2;
pll lazy1;
};
Seg seg[maxn << 2];
void merge(int v)
{
seg[v].l = seg[v << 1].l;
seg[v].r = seg[v << 1 | 1].r;
}
//void shift(int v, int l, int r);
void update1(int v, int l, int r, ll a, ll b){
seg[v].l = a + b * l;
seg[v].r = a + b * (r-1);
seg[v].lazy1 = {a, b};
}
void update2(int v, int l, int r, ll val){
seg[v].l += val;
seg[v].r += val;
seg[v].lazy1.F += val;
seg[v].lazy2 += val;
}
void shift(int v, int l, int r){
if (seg[v].lazy2 == 0 && seg[v].lazy1.S == -1) return;
int mid = (l + r) >> 1;
if (seg[v].lazy2 != 0){
update2(v << 1, l, mid, seg[v].lazy2);
update2(v << 1 | 1, mid, r, seg[v].lazy2);
}
if (seg[v].lazy1.S != -1){
update1(v << 1, l, mid, seg[v].lazy1.F, seg[v].lazy1.S);
update1(v << 1 | 1, mid, r, seg[v].lazy1.F, seg[v].lazy1.S);
}
seg[v].lazy1 = {0, -1};
seg[v].lazy2 = 0;
}
void change(int v, int l, int r, int ql, int qr, ll a, ll b){
// if (v == 1) debug(ql, qr, a, b);
if (qr <= l || r <= ql) return;
if (!(ql <= l && r <= qr)){
shift(v, l, r);
int mid = (l + r) >> 1;
change(v << 1, l, mid, ql, qr, a, b);
change(v << 1 | 1, mid, r, ql, qr, a, b);
}
else{
// debug(v, l, r, ql, qr, a, b, seg[v].l, seg[v].r);
if (a + b * l <= seg[v].l && a + b * (r-1) <= seg[v].r){
// debug(seg[v].l, seg[v].r, seg[v].mx, seg[v].lazy1.F, seg[v].lazy1.S);
update1(v, l, r, a, b);
return;
}
if (a + b * l >= seg[v].l && a + b * (r-1) >= seg[v].r) return;
shift(v, l, r);
int mid = (l + r) >> 1;
change(v << 1, l, mid, ql, qr, a, b);
change(v << 1 | 1, mid, r, ql, qr, a, b);
}
merge(v);
//seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
void add(int v, int l, int r, int ql, int qr, ll val){
//if (v == 1) debug(ql, qr, val);
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
// debug(v, l, r, ql, qr, val);
update2(v, l, r, val);
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
add(v << 1, l, mid, ql, qr, val);
add(v << 1 | 1, mid, r, ql, qr, val);
merge(v);
//seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
ll get(int v, int l, int r, int idx){
//if (v == 1) debug(idx);
if (l + 1 == r) return seg[v].l;
shift(v, l, r);
int mid = (l + r) >> 1;
if (idx < mid) return get(v << 1, l, mid, idx);
else return get(v << 1 | 1, mid, r, idx);
}
const int lg = 20;
const ll inf = 1e18;
int n, q, h[maxn], queryl[maxn], queryr[maxn];
ll ans[maxn];
pii rmq[lg][maxn];
vector<pair<pii,int>> Q[maxn];
pii getmx(int l, int r){
r++;
int x = 31 - __builtin_clz(r-l);
return max(rmq[x][l], rmq[x][r-(1<<x)]);
}
void carttree(int l, int r){
if (r < l) return;
int mid = getmx(l, r).S;
mid = abs(mid);
carttree(l, mid-1);
carttree(mid+1, r);
// debug(x, y);
for (auto [tmp, idx]: Q[mid]){
ans[idx] = min(ans[idx], get(1, 0, n, tmp.S) + 1ll * (mid-tmp.F+1) * h[mid]);
}
add(1, 0, n, mid, r+1, 1ll * (mid-l+1) * h[mid]);
if (l == mid) return;
ll tmp = get(1, 0, n, mid-1);
tmp -= 1ll * (mid-1) * h[mid];
change(1, 0, n, mid, r+1, tmp, h[mid]);
}
void solve(bool flg){
vector<pii> val;
for (int i = 0; i < n; i++){
Q[i].clear();
}
for (int i = 1; i < 4*maxn; i++){
seg[i].l = 0;
seg[i].r = 0;
seg[i].lazy1 = {0, -1};
seg[i].lazy2 = 0;
}
for (int i = 0; i < n; i++){
if (!flg){
rmq[0][i] = {h[i], i};
}
else{
rmq[0][i] = {h[i], -i};
}
}
for (int i = 1; i < lg; i++){
for (int j = 0; j + (1 << i) <= n; j++){
rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
}
}
for (int i = 0; i < q; i++){
int mx = abs(getmx(queryl[i], queryr[i]).S);
Q[mx].push_back({{queryl[i], queryr[i]}, i});
}
carttree(0, n-1);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
for (int i = 0; i < n; i++){
h[i] = H[i];
}
for (int i = 0; i < q; i++){
queryl[i] = L[i];
queryr[i] = R[i];
ans[i] = inf;
}
solve(false);
// debug("----------------");
// for (int i = 0; i < q; i++) debug(i, ans[i]);
for (int i = 0; i < q; i++){
queryl[i] = n-R[i]-1;
queryr[i] = n-L[i]-1;
}
for (int i = 0; i < n/2; i++){
swap(h[i], h[n-i-1]);
}
solve(true);
vector<ll> res;
for (int i = 0; i < q; i++) res.push_back(ans[i]);
return res;
}
