#include "meetings.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 1e6+10;
ll eval(const pll &f, ll x) { return f.first * x + f.second; }
namespace seg {
struct node {
pll val;
ll lzy;
ll fst, lst;
bool leaf;
} t[N*4];
int sz;
void init(int n) {
sz = n;
t[0].val = {};
t[0].lzy = 0;
t[0].fst = 0;
t[0].lst = 0;
t[0].leaf = 1;
}
void up(int i, ll x) {
t[i].val.second += x;
t[i].lzy += x;
t[i].fst += x;
t[i].lst += x;
}
void ppg(int i, int b, int e) {
if (t[i].leaf) {
t[2*i+1] = t[2*i+2] = t[i];
t[2*i+1].lst = eval(t[2*i+1].val, (b+e)/2-1);
t[2*i+2].fst = eval(t[2*i+2].val, (b+e)/2);
t[i].leaf = 0;
} else {
up(2*i+1, t[i].lzy);
up(2*i+2, t[i].lzy);
}
t[i].lzy = 0;
}
void merge(int i) {
t[i].fst = t[2*i+1].fst;
t[i].lst = t[2*i+2].lst;
}
void add(int l, int r, ll x, int i, int b, int e) {
if (l <= b && e <= r) {
up(i, x);
return;
}
ppg(i, b, e);
if (l < (b+e)/2)
add(l, r, x, 2*i+1, b, (b+e)/2);
if ((b+e)/2 < r)
add(l, r, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void add(int l, int r, ll x) { add(l, r, x, 0, 0, sz); }
void mn(int l, int r, pll f, int i, int b, int e) {
ll fst2 = eval(f, b);
ll lst2 = eval(f, e-1);
if (l <= b && e <= r && t[i].fst >= fst2 && t[i].lst >= lst2) {
t[i].val = f;
t[i].fst = fst2;
t[i].lst = lst2;
t[i].leaf = 1;
return;
}
if (l <= b && e <= r && t[i].lst <= lst2 && t[i].fst <= fst2)
return;
ppg(i, b, e);
if (l < (b+e)/2)
mn(l, r, f, 2*i+1, b, (b+e)/2);
if ((b+e)/2 < r)
mn(l, r, f, 2*i+2, (b+e)/2, e);
merge(i);
}
void mn(int l, int r, pll f) { mn(l, r, f, 0, 0, sz); }
ll get(int p, int i, int b, int e) {
if (t[i].leaf)
return eval(t[i].val, p);
ppg(i, b, e);
if (p < (b+e)/2)
return get(p, 2*i+1, b, (b+e)/2);
else
return get(p, 2*i+2, (b+e)/2, e);
}
ll get(int p) { return get(p, 0, 0, sz); }
}
namespace rmq {
const int lg = 20;
pii mx[lg][N];
void make(vector<int> a) {
int n = a.size();
Loop (i,0,n)
mx[0][i] = {a[i], i};
Loop (i,0,lg-1) {
for (int j = 0; j + (2 << i) <= n; ++j)
mx[i+1][j] = max(mx[i][j], mx[i][j+(1<<i)]);
}
}
pii get(int l, int r) {
int k = __lg(r-l);
return max(mx[k][l], mx[k][r-(1<<k)]);
}
}
ll arr[N];
namespace cart {
pii t[N];
vector<pair<ll *, int>> queryl[N];
vector<pair<ll *, int>> queryr[N];
int rt;
int sz;
void make(int &ans, int l, int r) {
if (l >= r) {
ans = -1;
return;
}
ans = rmq::get(l, r).second;
make(t[ans].first, l, ans);
make(t[ans].second, ans+1, r);
}
void make(int n) { sz = n; make(rt, 0, sz); }
void dfs(int v, int l, int r, void (*merge)(int, int, int)) {
if (v == -1)
return;
dfs(t[v].first, l, v, merge);
dfs(t[v].second, v+1, r, merge);
merge(v, l, r);
}
void mergel(int v, int l, int r) {
seg::add(v, r, (v-l+1)*arr[v]);
if (v != l) {
ll x = seg::get(v-1);
seg::mn(v, r, pll{arr[v], x - (v-1)*arr[v]});
}
for (auto [p, pos] : queryl[v])
*p = seg::get(pos);
}
void merger(int v, int l, int r) {
seg::add(l, v+1, (r-v)*arr[v]);
if (v != r-1) {
ll x = seg::get(v+1);
seg::mn(l, v+1, pll{-arr[v], x + (v+1)*arr[v]});
}
for (auto [p, pos] : queryr[v])
*p = seg::get(pos);
}
void answer() {
seg::init(sz);
dfs(rt, 0, sz, mergel);
seg::init(sz);
dfs(rt, 0, sz, merger);
}
}
ll Ql[N], Qr[N];
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int n = H.size();
Loop (i,0,n)
arr[i] = H[i];
rmq::make(H);
cart::make(n);
int q = L.size();
Loop (i,0,q) {
int l = L[i];
int r = R[i]+1;
int v = rmq::get(l, r).second;
if (l < v) {
cart::queryr[cart::t[v].first]
.push_back({&Ql[i], l});
}
if (v < r-1) {
cart::queryl[cart::t[v].second]
.push_back({&Qr[i], r-1});
}
}
cart::answer();
vector<ll> ans(q);
Loop (i,0,q) {
int l = L[i];
int r = R[i]+1;
int v = rmq::get(l, r).second;
ans[i] = arr[v] * (r-l);
if (l < v)
ans[i] = min(ans[i], Ql[i] + arr[v] * (r-v));
if (v < r-1)
ans[i] = min(ans[i], Qr[i] + arr[v] * (v-l+1));
}
return ans;
}
