#include "meetings.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 750005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct query{
int l, r, id;
query(){l = r = id = 0;}
query(int a, int b, int c){l = a, r = b, id = c;}
};
struct segtree{
pii seg[4*maxn];
void init(int cur, int l, int r, vector<int> &h) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = {h[l], l};
return;
}
int m = (l + r) / 2;
init(cur*2, l, m, h), init(cur*2+1, m, r, h);
seg[cur] = max(seg[cur*2], seg[cur*2+1]);
}
pii query(int cur, int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return {-1, 0};
if (ql <= l && qr >= r) return seg[cur];
int m = (l + r) / 2;
return max(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
}
} tr;
struct LINE{
ll m, k;
LINE() {m = 0, k = 0;}
LINE(ll x, ll y){m = x, k = y;}
ll val(ll x){return m*x + k;}
} line[maxn];
int lc[maxn], rc[maxn], lef[maxn], rig[maxn];
vector<int> ord;
vector<query> qs[maxn];
void dfs(int n) {
if (lc[n] != -1) dfs(lc[n]);
if (rc[n] != -1) dfs(rc[n]);
ord.push_back(n);
}
set<int> se;
ll tag[maxn];
vector<ll> solve(vector<int> h, vector<query> que) {
int n = h.size(), q = que.size();
tr.init(1, 0, n, h);
se.clear();
for (int i = 0;i < n;i++) {
se.insert(i);
lc[i] = rc[i] = -1;
lef[i] = 0, rig[i] = n - 1;
tag[i] = 0;
line[i] = LINE();
qs[i].clear();
}
se.insert(n);
for (auto x:que) {
int ind = tr.query(1, 0, n, x.l, x.r+1).ss;
qs[ind].push_back(x);
}
stack<int> stk;
for (int i = 0;i < n;i++) {
while (stk.size() && h[i] >= h[stk.top()]) {
lc[i] = stk.top();
rig[stk.top()] = i-1;
stk.pop();
}
if (stk.size()) {
rc[stk.top()] = i;
lef[i] = stk.top()+1;
}
stk.push(i);
}
int root = 0;
while (stk.size() > 1) stk.pop();
root = stk.top();
ord.clear();
dfs(root);
vector<ll> ret(q, inf);
for (int i:ord) {
for (auto [l, r, id]:qs[i]) {
ret[id] = (ll)(h[i]) * (r - l + 1);
if (rc[i] != -1) {
int ind = *prev(se.upper_bound(r));
//debug(l, r, ind, line[ind].m, line[ind].k, tag[rc[i]], line[ind].val(r) + tag[rc[i]]);
ret[id] = min(ret[id], (ll)h[i] * (i - l + 1) + line[ind].val(r) + tag[rc[i]]);
}
}
ll delta = (ll)(i - lef[i] + 1) * h[i];
bool hasl = lc[i] != -1, hasr = rc[i] != -1;
if (hasl) {
int ind = *prev(se.lower_bound(i));
line[i].k = h[i] + line[ind].val(i);
} else {
line[i].k = h[i];
}
if (hasl || hasr) {
if (rc[i] != -1) tag[rc[i]] += delta;
if (i - lef[i] < rig[i] - i) {
for (int j = lef[i];j < i;j++) {
line[j].k += tag[lc[i]] - tag[rc[i]];
}
line[i].k += tag[i] - tag[rc[i]];
tag[i] = tag[rc[i]];
} else {
for (int j = i+1;j <= rig[i];j++) {
line[j].k += tag[rc[i]] - tag[lc[i]];
}
line[i].k += tag[i] - tag[lc[i]];
tag[i] = tag[lc[i]];
}
}
if (hasr) {
LINE mi = LINE(h[i], line[i].val(i) - (ll)i * h[i]);
//debug(i, mi.m, mi.k, mi.val(i) + tag[i]);
auto it = next(se.lower_bound(i));
auto div = [&] (ll a, ll b){
assert(b != 0);
if (b < 0) a = -a, b = -b;
return a / b + 1;
};
vector<int> rem;
while (*it < n) {
int r = (*next(it)) - 1, l = *it;
if (mi.val(r) <= line[*it].val(r)) {
rem.push_back(l);
} else if (mi.val(l) > line[l].val(l)) {
break;
} else {
rem.push_back(l);
int pnt = div(line[l].k - mi.k, mi.m - line[l].m);
se.insert(pnt);
line[pnt] = line[l];
break;
}
it = next(it);
}
for (auto j:rem) se.erase(j);
line[i] = mi;
}
}
return ret;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
vector<query> que;
int n = H.size(), q = L.size();
for (int i = 0;i < q;i++) {
que.push_back(query(L[i], R[i], i));
}
vector<ll> ret(q, inf);
vector<ll> tmp = solve(H, que);
ret = tmp;
reverse(H.begin(), H.end());
for (int i = 0;i < q;i++) {
que[i].l = n - 1 - que[i].l, que[i].r = n - 1 - que[i].r;
swap(que[i].l, que[i].r);
}
tmp = solve(H, que);
for (int i = 0;i < q;i++) ret[i] = min(ret[i], tmp[i]);
return ret;
}
/*
6 3
2 4 3 5 3 1
0 5
1 3
2 5
*/
