// Be name khode //
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
const int maxn5 = 75e4 + 5;
const int maxnt = 4e6 + 5;
const int lg = 20;
const ll inf = 1e18;
int n, newnode = 2, curpt = 0;
vector <ll> ret;
ll a[maxn5];
pair <ll, pair<ll, ll>> av[maxn5 * lg * 2];
namespace rmq{
pair <int, int> mx[lg][maxn5];
void build(int n){
for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
mx[i][j] = max(mx[i - 1][j], (j + (1 << (i - 1))) < n ? mx[i - 1][j + (1 << (i - 1))] : mp(-1, -1));
}
int get_max(int l, int r){
int k = 31 - __builtin_clz(r - l + 1);
return max(mx[k][l], mx[k][r - (1 << k) + 1]).se;
}
}
struct cht{
int ptl = 0, ptr = 0;
ll inter(pair <ll, ll> a, pair <ll, ll> b){
if(a.se == b.se)
return a.fi > b.fi ? inf : -inf;
//cout << a.fi << ' ' << a.se << ' ' << b.fi << ' ' << b.se << endl;
return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
}
void add(ll cons, ll sh){
ll st = -inf;
while(ptr > ptl && (st = inter(av[ptr - 1].se, mp(cons, sh))) <= av[ptr - 1].fi)
ptr--;
if(ptr == ptl)
st = -inf;
//cout << "ha? " << cons << ' ' << sh << ' ' << st << ' ' << av.size() << endl;
//cout << (-122) / 46 << endl;
//cout << "ha? " << cons << ' ' << sh << ' ' << ptr << ' ' << av.size() << endl;
av[ptr++] = {st, {cons, sh}};
}
ll get(ll x){
if(ptl == ptr)
return -inf;
int pt2 = upper_bound(av + ptl, av + ptr, mp(x, mp(inf, inf))) - av - 1;
//cout << "we all gor " << pt << ' ' << av[pt].se.fi << ' ' << av[pt].se.se << ' ' << av.size() << endl;
//cout << av.back().fi << ' ' << x << endl;
//cout << av.back().se.fi << ' ' << av.back().se.se << endl;
return av[pt2].se.fi + av[pt2].se.se * x;
}
} seg[maxnt];
int ch[2][maxnt], cnt[maxnt];
ll lazy[maxnt];
struct segment{
segment(){
memset(lazy, 0, sizeof lazy);
}
void build(int l, int r, int v){
cnt[v] += (r - l == 1);
seg[v].ptl = seg[v].ptr = curpt;
curpt += cnt[v];
if(r - l == 1){
seg[v].add(0, 0);
return;
}
int mid = (l + r) >> 1;
if(!ch[0][v])
ch[0][v] = newnode++;
if(!ch[1][v])
ch[1][v] = newnode++;
build(l, mid, ch[0][v]);
build(mid, r, ch[1][v]);
}
void sch(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
cnt[v]++;
return;
}
int mid = (l + r) >> 1;
if(!ch[0][v])
ch[0][v] = newnode++;
if(!ch[1][v])
ch[1][v] = newnode++;
sch(l, mid, lq, rq, ch[0][v]);
sch(mid, r, lq, rq, ch[1][v]);
}
void add_cht(int l, int r, int lq, int rq, pair <ll, ll> val, int v){
if(rq <= l || r <= lq)
return;
//cout << "there's " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val.fi << ' ' << val.se << ' ' << v << ' ' << lazy[v] << endl;
val.fi += lazy[v];
if(lq <= l && r <= rq){
//cout << "baba " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << cnt[v] << ' ' << val.fi << ' ' << val.se << endl;
seg[v].add(val.fi, val.se);
return;
}
int mid = (l + r) >> 1;
add_cht(l, mid, lq, rq, val, ch[0][v]);
add_cht(mid, r, lq, rq, val, ch[1][v]);
}
void add(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq)
return;
//cout << "adding " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val << ' ' << v << endl;
if(lq <= l && r <= rq){
lazy[v] += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, ch[0][v]);
add(mid, r, lq, rq, val, ch[1][v]);
}
ll get(int l, int r, int id, int v){
ll ret = (-seg[v].get(id)) + lazy[v];
//cout << "look " << l << ' ' << r << ' ' << v << ' ' << ret << ' ' << lazy[v] << ' ' << id << endl;
if(r - l == 1)
return ret;
int mid = (l + r) >> 1;
if(abs(id) < mid)
ret = min(ret, get(l, mid, id, ch[0][v]) + lazy[v]);
else
ret = min(ret, get(mid, r, id, ch[1][v]) + lazy[v]);
//cout << "fina " << l << ' ' << r << ' ' << ret << ' ' << lazy[v] << endl;
return ret;
}
} pre, suf;
vector <pair<pair<int, int>, int>> req[maxn5];
void cartesian(int l, int r){
if(r - l == 1){
for(auto [p, id] : req[l])
ret[id] = a[l];
pre.add(0, n, l, l + 1, a[l], 0);
suf.add(0, n, l, l + 1, a[l], 1);
return;
}
int mx = rmq::get_max(l, r - 1);
if(l < mx)
cartesian(l, mx);
if(mx + 1 < r)
cartesian(mx + 1, r);
//cout << "in " << l << ' ' << r << ' ' << mx << endl;
for(auto [p, id] : req[mx]){
int lq = p.fi, rq = p.se;
ret[id] = (rq - lq + 1) * a[mx];
//cout << ret[id] << endl;
if(lq < mx)
ret[id] = min(ret[id], suf.get(0, n, lq, 1) + (rq - mx + 1) * a[mx]);
//cout << ret[id] << endl;
if(rq > mx)
ret[id] = min(ret[id], pre.get(0, n, -rq, 0) + (mx - lq + 1) * a[mx]);
//cout << ret[id] << endl;
}
ll keeppre = (l < mx ? pre.get(0, n, -(mx - 1), 0) : 0);
ll keepsuf = (mx + 1 < r ? suf.get(0, n, mx + 1, 1) : 0);
//cout << "in " << l << ' ' << r << ' ' << mx << ' ' << keepsuf << ' ' << keeppre << endl;
pre.add(0, n, mx, r, (mx - l + 1) * a[mx], 0);
suf.add(0, n, l, mx + 1, (r - mx) * a[mx], 1);
pre.add_cht(0, n, mx, r, mp(-(keeppre + (1 - mx) * a[mx]), a[mx]), 0);
//cout << "all here " << endl;
suf.add_cht(0, n, l, mx + 1, mp(-(keepsuf + (1 + mx) * a[mx]), a[mx]), 1);
//cout << "all done " << l << ' ' << r << endl;
}
void pre_cartesian(int l, int r){
if(r - l <= 1)
return;
int mid = rmq::get_max(l, r - 1);
pre_cartesian(l, mid);
pre_cartesian(mid + 1, r);
pre.sch(0, n, mid, r, 0);
suf.sch(0, n, l, mid + 1, 1);
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
std::vector<int> r) {
n = h.size();
for(int i = 0; i < n; i++)
a[i] = h[i];
int q = l.size();
ret.resize(q);
for(int i = 0; i < n; i++)
rmq::mx[0][i] = mp(h[i], i);
rmq::build(n);
for(int i = 0; i < q; i++){
int mx = rmq::get_max(l[i], r[i]);
req[mx].pb({{l[i], r[i]}, i});
}
pre_cartesian(0, n);
pre.build(0, n, 0);
suf.build(0, n, 1);
cartesian(0, n);
return ret;
}
