#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
vector<int> h;
const int MAX_L = 20;
const int MAX_N = 750000;
int rmq[MAX_L][MAX_N];
int rmqlg[1+MAX_N];
static inline int argmax(int a, int b) {
if(h[a] >= h[b])
return a;
return b;
}
void initrmq(int n) {
for(int i = 0; i < n; ++i)
rmq[0][i] = i;
for(int i = 2; i <= n; ++i)
rmqlg[i] = rmqlg[i / 2] + 1;
for(int l = 1; l < MAX_L; ++l)
for(int i = 0; i < n - (1 << l) + 1; ++i)
rmq[l][i] = argmax(rmq[l - 1][i], rmq[l - 1][i + (1 << (l - 1))]);
}
int queryRmq(int a, int b) {
int s = (b - a + 1);
int l = rmqlg[s];
return argmax(rmq[l][a], rmq[l][b - (1 << l) + 1]);
}
struct RangeSet {
set<int> x;
long long lazy[1+4*MAX_N];
int rangeR[MAX_N];
long long yinter[MAX_N];
long long slope[MAX_N];
void clear() {
for(int i = 0; i <= 4*MAX_N; ++i)
lazy[i] = 0;
for(int i = 0; i < MAX_N; ++i)
rangeR[i] = yinter[i] = slope[i] = 0;
}
void pushlazy(int nod, int l, int r) {
if(l == r)
yinter[l] += lazy[nod];
else {
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
void getlazy(int poz, int l = 0, int r = MAX_N - 1, int nod = 1) {
if(r < poz || poz < l || r < l) return;
pushlazy(nod, l, r);
if(l < r) {
int mid = (l + r) / 2;
getlazy(poz, l, mid, 2 * nod);
getlazy(poz, mid + 1, r, 2 * nod + 1);
}
}
void addRange(int i, int j, long long val, int l = 0, int r = MAX_N - 1, int nod = 1) {
if(r < i || j < l || j < i || r < l) return;
if(i <= l && r <= j)
lazy[nod] += val;
else {
int mid = (l + r) / 2;
addRange(i, j, val, l, mid, 2 * nod);
addRange(i, j, val, mid + 1, r, 2 * nod + 1);
}
}
void insertRange(int st, int dr, long long yinterU, long long slopeU) {
getlazy(st);
rangeR[st] = dr;
yinter[st] = yinterU;
slope[st] = slopeU;
x.insert(st);
}
void eraseRange(int st) {
x.erase(st);
}
long long getDp(int i) {
if(x.size() == 0) return 0LL;
set<int>::iterator it = x.upper_bound(i);
if(it == x.begin()) return 0LL;
it--;
if(rangeR[*it] < i) return 0LL;
getlazy(*it);
return yinter[*it] + (i - *it) * slope[*it];
}
long long forceEval(int i, int j) {
getlazy(i);
return yinter[i] + (j - i) * slope[i];
}
} ranges;
struct Query {
int l, r, i;
};
vector<Query> queries[MAX_N];
vector<long long> rezq;
int ctreeL[MAX_N], ctreeR[MAX_N];
int buildctree(int l, int r, int dep = 0) {
if(l <= r) {
int root = queryRmq(l, r);
ctreeL[root] = buildctree(l, root - 1, dep + 1);
ctreeR[root] = buildctree(root + 1, r, dep + 1);
return root;
}
return -1;
}
void compress(int nod, int r, long long yinter, long long slope, long long cst) {
int i = nod + 1;
while(i <= r && slope * (ranges.rangeR[i] - nod) + yinter <=
ranges.forceEval(i, ranges.rangeR[i]) + cst) {
ranges.eraseRange(i);
i = ranges.rangeR[i] + 1;
}
if(i <= r && slope * (i - nod) + yinter <= ranges.forceEval(i, i) + cst) {
int st = i, dr = ranges.rangeR[i];
while(dr - st > 1) {
int mid = (dr + st) / 2;
if(slope * (mid - nod) + yinter <=
ranges.slope[i] * (mid - i) + ranges.yinter[i] + cst)
st = mid;
else
dr = mid;
}
long long dp = ranges.getDp(dr);
ranges.eraseRange(i);
ranges.insertRange(dr, ranges.rangeR[i], dp, ranges.slope[i]);
i = dr;
}
if(nod + 1 <= i - 1) ranges.insertRange(nod + 1, i - 1, yinter + slope, slope);
ranges.addRange(i, r, cst);
}
vector<int> stacknod, stackl, stackr;
vector<bool> dfsd;
static inline void pushState(int nod, int l, int r, bool state) {
stacknod.push_back(nod);
stackl.push_back(l);
stackr.push_back(r);
dfsd.push_back(state);
}
void popState() {
stacknod.pop_back();
stackl.pop_back();
stackr.pop_back();
dfsd.pop_back();
}
void ctreedfs(int nod, int l, int r) {
bool state;
pushState(nod, l, r, false);
while(!stacknod.empty()) {
nod = stacknod.back(), l = stackl.back(), r = stackr.back();
state = dfsd.back();
popState();
if(nod != -1) {
if(!state) {
pushState(nod, l, r, true);
pushState(ctreeL[nod], l, nod - 1, false);
pushState(ctreeR[nod], nod + 1, r, false);
} else {
for(auto it: queries[nod])
rezq[it.i] = min(rezq[it.i],
ranges.getDp(it.r) + (long long)h[nod] * (nod - it.l + 1));
compress(nod, r, ranges.getDp(nod - 1) + h[nod], h[nod], (long long)(nod - l + 1) * h[nod]);
ranges.insertRange(nod, nod, ranges.getDp(nod - 1) + h[nod], 0);
}
}
}
}
void solve(int n, int q, const vector<int> &l, const vector<int> &r) {
initrmq(n);
for(int i = 0; i < n; ++i)
queries[i].clear();
for(int i = 0; i < q; ++i) {
int root = queryRmq(l[i], r[i]);
queries[root].push_back({l[i], r[i], i});
}
ranges.clear();
int root = buildctree(0, n - 1);
ctreedfs(root, 0, n - 1);
}
vector<long long> minimum_costs(vector<int> _h, vector<int> l, vector<int> r) {
int n = _h.size();
int q = l.size();
h = _h;
rezq.resize(q, 1LL << 60);
solve(n, q, l, r);
reverse(h.begin(), h.end());
for(int i = 0; i < q; ++i) {
swap(l[i], r[i]);
l[i] = n - 1 - l[i];
r[i] = n - 1 - r[i];
}
solve(n, q, l, r);
return rezq;
}
