#include "meetings.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Seg{
int cap;
vector<pair<ll, int>> seg;
void init(vector<ll> v){
for(cap = 1; cap < sz(v); cap *= 2);
seg.resize(2*cap);
for(int i = 0; i < cap; i++) seg[i+cap].second = i;
for(int i = 0; i < sz(v); i++) seg[i+cap].first = v[i];
for(int i = cap-1; i >= 1; --i) seg[i] = max(seg[2*i], seg[2*i+1]);
}
pair<ll, int> qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return seg[i];
if(b < l || r < a) return {-INF, -1};
int m = (a+b)/2;
return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}
int argmax(int l, int r){return qry(l, r, 1, cap, 1).second;}
};
vector<ll> H;
vector<int> lc, rc;
struct Lin{
ll a, b; // a + b*x
};
set<pair<int, int>> s;
vector<Lin> lin;
vector<ll> add;
vector<ll> answer;
vector<vector<tuple<int, int, int>>> query;
ll get(int i){
int j = (--s.lower_bound({i+1, 0}))->first;
return lin[j].a + lin[j].b*(i-j);
}
void calc(int i, int start, int end){
if(lc[i] != -1) calc(lc[i], start, i-1);
if(rc[i] != -1) calc(rc[i], i+1, end);
for(auto [L, R, ind] : query[i]){
answer[ind] = H[i]*(i+1-L) + (R>i ? add[rc[i]]+get(R) : 0);
}
if(lc[i] == -1 && rc[i] == -1){
s.emplace(i, i);
lin[i] = {H[i], 0};
}
else if(rc[i] == -1){
s.emplace(i, i);
lin[i] = {H[i]+get(i-1), 0};
add[i] = add[lc[i]];
}
else if(lc[i] == -1){
s.emplace(i, i);
add[i] = add[rc[i]]+H[i];
lin[i] = {H[i]-add[i], 0};
}
else{
s.emplace(i, i);
lin[i] = {H[i]+get(i-1), 0};
ll le = lin[i].a + add[lc[i]];
int until = end;
auto it = s.lower_bound({i+1, 0});
while(it != s.end() && it->first <= end){
Lin li = lin[it->first];
ll y = add[rc[i]] + li.a + li.b*(it->second-it->first);
// cerr << le + (it->second-i)*H[i] << " " << y + (i+1-start)*H[i] << "\n";
if(le + (it->second-i)*H[i] <= y + (i+1-start)*H[i]) it = s.erase(it);
else{
int j = int(((2*i+1-start)*H[i]+add[rc[i]]+li.a-li.b*it->first-le)/(H[i]-li.b))+1;
// cerr << j << " " << le << " " << add[rc[i]] << " " << lin[it->first].a << " " << lin[it->first].b << "\n";
int r = it->second;
assert(j <= r);
until = max(j, it->first)-1;
if(j > it->first){
lin[j] = {li.a+li.b*(j-it->first), li.b};
s.erase(it);
s.emplace(j, r);
}
break;
}
}
// cerr << le << "\n";
add[rc[i]] += (i+1-start)*H[i];
if(until > i){
s.emplace(i+1, until);
lin[i+1] = {le-add[rc[i]]+H[i], H[i]};
}
if(i-start < end-i){
add[i] = add[rc[i]];
it = s.lower_bound({start, 0});
for(; it != s.end() && it->first <= i; it++){
lin[it->first].a += add[lc[i]]-add[i];
}
}
else{
add[i] = add[lc[i]];
it = s.lower_bound({i+1, 0});
for(; it != s.end() && it->first <= end; it++){
lin[it->first].a += add[rc[i]]-add[i];
}
}
}
// cerr << "## " << i << " ##\n";
// auto it = s.lower_bound({start, 0});
// cerr << lc[i] << " " << rc[i] << " " << add[i] << "\n";
// for(; it != s.end() && it->first <= end; it++){
// cerr << it->first << " " << it->second << " " << lin[it->first].a << " " << lin[it->first].b << "\n";
// }
}
vector<ll> solve(int n, int q, int root){
s.clear();
answer.assign(q, 0);
add.assign(n, 0);
calc(root, 0, n-1);
return answer;
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
int n = sz(h);
int q = sz(L);
H.resize(n);
for(int i = 0; i < n; i++) H[i] = h[i];
lc.assign(n, -1);
rc.assign(n, -1);
stack<pair<int, int>> st;
for(int i = 0; i < n; i++){
while(!st.empty() && st.top().first <= H[i]){
lc[i] = st.top().second;
st.pop();
}
if(!st.empty()) rc[st.top().second] = i;
st.emplace(H[i], i);
}
Seg seg;
seg.init(H);
query.clear();
query.resize(n);
lin.resize(n);
add.assign(n, 0);
for(int i = 0; i < q; i++){
int j = seg.argmax(L[i]+1, R[i]+1);
// cerr << j << "\n";
query[j].emplace_back(L[i], R[i], i);
}
int root = seg.argmax(1, n);
vector<ll> ans = solve(n, q, root);
reverse(H.begin(), H.end());
for(int i = 0; i < q; i++){
int l = L[i];
L[i] = n-1-R[i];
R[i] = n-1-l;
}
for(int i = 0; i < n-i; i++){
swap(lc[i], lc[n-1-i]);
swap(rc[i], rc[n-1-i]);
swap(query[i], query[n-1-i]);
}
for(int i = 0; i < n; i++){
swap(lc[i], rc[i]);
if(lc[i] != -1) lc[i] = n-1-lc[i];
if(rc[i] != -1) rc[i] = n-1-rc[i];
for(auto& [l, r, ind] : query[i]){
int temp = l;
l = n-1-r;
r = n-1-temp;
}
}
vector<ll> ans2 = solve(n, q, n-1-root);
vector<ll> C(q);
for(int i = 0; i < q; i++) C[i] = min(ans[i], ans2[i]);//, cerr << ans[i] << " " << ans2[i] << "\n";
return C;
}
