#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int MAX_N = 750000;
const int MAX_L = 19;
vector<int> h;
int rmq[MAX_L][MAX_N];
int rmqlg[1+MAX_N];
int argmax(int a, int b) {
if(h[a] >= h[b])
return a;
return b;
}
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 Query {
int l, r, i;
};
vector<long long> rez;
vector<Query> queries[MAX_N];
struct Range {
int l, r;
long long yinter, slope;
};
struct Cell {
long long lazy;
deque<Range> ranges;
long long getDp(int i) {
if(ranges.size() == 0) return 0LL;
int st = 0, dr = ranges.size();
while(dr - st > 1) {
int mid = (st + dr) / 2;
if(ranges[mid].l <= i)
st = mid;
else
dr = mid;
}
return lazy + ranges[st].yinter + ranges[st].slope * (i - ranges[st].l);
}
};
void heavyMerge(Cell &st, Cell &dr, Cell &dest) {
if(st.ranges.size() < dr.ranges.size()) {
dest.ranges.swap(dr.ranges);
dest.lazy = dr.lazy;
for(int i = st.ranges.size() - 1; i >= 0; --i) {
dest.ranges.push_front(st.ranges[i]);
dest.ranges.front().yinter += st.lazy - dest.lazy;
}
} else {
dest.ranges.swap(st.ranges);
dest.lazy = st.lazy;
for(int i = 0; i < dr.ranges.size(); ++i) {
dest.ranges.push_back(dr.ranges[i]);
dest.ranges.back().yinter += dr.lazy - dest.lazy;
}
}
}
int intersect(long long a1, long long b1, long long c1,
long long a2, long long b2, long long c2) {
return (b2 - a2 * c2 - b1 + c1 * a1) / (a1 - a2);
}
int intersect2(long long a1, long long b1, long long c1,
long long a2, long long b2, long long c2) {
return (b1 + a1 * c1 - b2 + a2 * c2 + a1 + a2 - 1) / (a1 + a2);
}
void prefCompress(Cell &pref, int root, long long yinter, long long slope, long long cst) {
int splitr = root;
// Elimin toate bucatile complete
while(!pref.ranges.empty() && yinter + slope * (pref.ranges.front().r - root) <=
pref.getDp(pref.ranges.front().r) + cst) {
splitr = pref.ranges.front().r;
pref.ranges.pop_front();
}
// Vad unde splituiesc ultima bucata
if(!pref.ranges.empty() && yinter + slope * (pref.ranges.front().l - root) <=
pref.getDp(pref.ranges.front().l) + cst) {
Range prt = pref.ranges.front();
splitr = intersect(slope, yinter, root,
prt.slope, prt.yinter + cst, prt.l);
pref.ranges.front().yinter = pref.getDp(splitr + 1) - pref.lazy;
pref.ranges.front().l = splitr + 1;
}
pref.lazy += cst;
if(root + 1 <= splitr) pref.ranges.push_front({root + 1, splitr, yinter + slope - pref.lazy, slope});
}
void suffCompress(Cell &suff, int root, long long yinter, long long slope, long long cst) {
int splitl = root;
// Elimin toate bucatile complete
while(!suff.ranges.empty() && yinter + slope * (root - suff.ranges.back().l) <=
suff.getDp(suff.ranges.back().l) + cst) {
splitl = suff.ranges.back().l;
suff.ranges.pop_back();
}
// Vad unde splituiesc ultima bucata
if(!suff.ranges.empty() && yinter + slope * (root - suff.ranges.front().l) <=
suff.getDp(suff.ranges.front().r) + cst) {
Range prt = suff.ranges.front();
splitl = intersect2(slope, yinter, root,
prt.slope, prt.yinter + cst, prt.l);
suff.ranges.back().r = splitl - 1;
}
suff.lazy += cst;
if(splitl <= root - 1) suff.ranges.push_back({splitl, root - 1, yinter + slope * (root - splitl) - suff.lazy, slope});
}
void solve(int l, int r, Cell &pref, Cell &suff) {
pref.lazy = suff.lazy = 0;
if(l <= r) {
int root = queryRmq(l, r);
Cell stSuff, stPref;
Cell drSuff, drPref;
solve(l, root - 1, stPref, stSuff);
solve(root + 1, r, drPref, drSuff);
for(auto it: queries[root])
rez[it.i] = min(drPref.getDp(it.r) + (long long)(root - it.l + 1) * h[root],
stSuff.getDp(it.l) + (long long)(it.r - root + 1) * h[root]);
prefCompress(drPref, root, stPref.getDp(l) + h[root], h[root], (long long)(root - l + 1) * h[root]);
suffCompress(stSuff, root, drSuff.getDp(r) + h[root], h[root], (long long)(r - root + 1) * h[root]);
stPref.ranges.push_back({root, root, stPref.getDp(root - 1) + h[root] - stPref.lazy, 1});
drSuff.ranges.push_front({root, root, drSuff.getDp(root + 1) + h[root] - drSuff.lazy, -1});
heavyMerge(stPref, drPref, pref);
heavyMerge(stSuff, drSuff, suff);
}
}
void solveQueries(int n) {
Cell st, dr;
solve(0, n - 1, st, dr);
}
vector<long long> minimum_costs(vector<int> _h, vector<int> l, vector<int> r) {
int n, q;
h = _h;
n = _h.size();
q = l.size();
rez.resize(q);
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))]);
for(int i = 0; i < q; ++i) {
int root = queryRmq(l[i], r[i]);
queries[root].push_back({l[i], r[i], i});
}
solveQueries(n);
return rez;
}
