#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct line {
int st, en;
ll m, b;
line() {}
line(int st_, int en_, ll m_, ll b_) : st(st_), en(en_), m(m_), b(b_) {}
ll eval(ll x){
return m * x + b;
}
};
vector<line> stuff;
struct line_container {
int st, en;
ll lazy;
line_container(int st_, int en_) : st(st_), en(en_), lazy(0) {}
line front(){
assert(size());
line l = stuff[st];
l.b += lazy;
return l;
}
line back(){
assert(size());
line l = stuff[en-1];
l.b += lazy;
return l;
}
ll eval_front(ll x){
assert(size());
return lazy + stuff[st].eval(x);
}
ll eval_back(ll x){
assert(size());
return lazy + stuff[en-1].eval(x);
}
ll at(int p){
assert(size() > 0);
int s = st, e = en;
while(e - s > 1){
int mid = (s + e) / 2;
if(stuff[mid].st <= p){
s = mid;
} else {
e = mid;
}
}
assert(stuff[s].st <= p && p < stuff[s].en);
return lazy + stuff[s].eval(p);
}
line pop_front(){
assert(size());
line l = stuff[st++];
l.b += lazy;
return l;
}
line pop_back(){
assert(size());
line l = stuff[--en];
l.b += lazy;
return l;
}
void push_back(line l){
l.b -= lazy;
stuff[en++] = l;
}
void push_front(line l){
l.b -= lazy;
stuff[--st] = l;
}
int size(){
return en-st;
}
};
int n;
int qnum;
vector<ll> ans;
vector<int> heights, ql, qr;
vector<pair<int, int> > key;
static const int S = 1 << 21;
vector<pair<pair<int, int>, int> > seg;
vector<vector<int> > queries;
pair<pair<int, int>, int> max_query(int l, int r){
pair<pair<int, int>, int> res(make_pair(0, -1), -1);
assert(max(0, l) < min(r, n));
for(int a = S+l, b = S+r; a < b; a /= 2, b /= 2){
if(a & 1){
res = max(res, seg[a]);
a++;
}
if(b & 1){
--b;
res = max(res, seg[b]);
}
}
return res;
}
line_container solve(int l, int r){
if(l >= r){
return line_container(l, l);
}
int x = max_query(l, r).second;
auto lcont = solve(l, x);
auto rcont = solve(x+1, r);
int cutoff = x+1;
for(auto j : queries[x]){
assert(l <= ql[j] && qr[j] < r);
ll a;
if(x == qr[j]){
a = 0;
} else if(x < qr[j]){
a = rcont.at(qr[j]);
} else assert(false);
ll cnd = ll(x - ql[j] + 1) * heights[x] + a;
ans[j] = min(ans[j], cnd);
}
rcont.lazy += heights[x] * ll(x - l + 1);
if(lcont.size()){
assert(lcont.back().en == x);
ll lback = lcont.eval_back(x-1);
while(rcont.size() > 0){
assert(lcont.size());
int st = rcont.front().st;
int en = rcont.front().en;
if(lback + (en - x) * ll(heights[x]) <= rcont.eval_front(en-1)){
cutoff = en;
rcont.pop_front();
continue;
}
int s = st-1, e = en-1;
while(e - s > 1){
int mid = (s + e) / 2;
ll lval = lback + (mid - x + 1) * ll(heights[x]);
ll rval = rcont.eval_front(mid);
if(lval > rval){
e = mid;
} else {
s = mid;
}
}
line bfront = rcont.pop_front();
bfront.st = e;
rcont.push_front(bfront);
cutoff = e;
break;
}
assert(x < cutoff);
lcont.push_back(line(x, cutoff, heights[x], lback - ll(x-1) * heights[x]));
} else {
lcont.push_back(line(x, x+1, heights[x], -ll(x-1) * heights[x]));
}
if(lcont.size() > rcont.size()){
while(rcont.size()){
lcont.push_back(rcont.pop_front());
}
return lcont;
} else {
while(lcont.size()){
rcont.push_front(lcont.pop_back());
}
return rcont;
}
}
void solve(){
for(int i = 0; i < n; i++){
seg[S+i] = make_pair(key[i], i);
}
for(int i = S-1; i >= 1; i--){
seg[i] = max(seg[2*i], seg[2*i+1]);
}
for(int i = 0; i < n; i++) queries[i].clear();
for(int i = 0; i < qnum; i++){
assert(ql[i] <= qr[i]);
if(ql[i] < qr[i]){
int x = max_query(ql[i], qr[i]+1).second;
queries[x].push_back(i);
}
}
solve(0, n);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
heights = H;
ql = L;
qr = R;
n = int(heights.size());
qnum = int(ql.size());
ans.assign(qnum, 1e18);
seg.resize(2*S);
queries.resize(n);
stuff.resize(n);
for(int i = 0; i < qnum; i++){
if(ql[i] == qr[i]){
ans[i] = heights[ql[i]];
}
}
key.resize(n);
for(int i = 0; i < n; i++){
key[i] = make_pair(heights[i], i);
}
for(int f = 0; f < 2; f++){
solve();
reverse(heights.begin(), heights.end());
reverse(key.begin(), key.end());
for(int i = 0; i < qnum; i++){
ql[i] = n-1-ql[i];
qr[i] = n-1-qr[i];
swap(ql[i], qr[i]);
}
}
return ans;
}
