#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
const ll infl = 1e18 + 110;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct SegmentTree{
//To change
struct Node{
//defaults
ll mn = 0, add = 0; bool marked = false;
void apply(ll val){
mn += val;
add += val;
marked = true;
}
};
void push(int x){
if(t[x].marked){
t[x << 1].apply(t[x].add);
t[x << 1 | 1].apply(t[x].add);
t[x].add = 0; t[x].marked = false;
}
}
Node merge(Node a, Node b){
Node res;
if(a.mn < b.mn){
res.mn = a.mn;
}else{
res.mn = b.mn;
}
return res;
}
Node neutral;
vector<Node> t;
int n;
//construction
void init(int _n){
n = _n;
t.assign(4 * n, neutral);
}
void build(vector<int> &a, int x, int lx, int rx){
if(lx == rx){
t[x].mn = a[lx];
return;
}
int mx = (lx + rx) >> 1;
build(a, x << 1, lx, mx);
build(a, x << 1 | 1, mx + 1, rx);
t[x] = merge(t[x << 1], t[x << 1 | 1]);
}
void upd(int x, int lx, int rx, int l, int r, int val){
if(rx < l || r < lx) return;
if(l <= lx && rx <= r){
t[x].apply(val); return;
}
push(x);
int mx = (lx + rx) >> 1;
upd(x << 1, lx, mx, l, r, val);
upd(x << 1 | 1, mx + 1, rx, l, r, val);
t[x] = merge(t[x << 1], t[x << 1 | 1]);
}
Node get(int x, int lx, int rx, int l, int r){
if(rx < l || r < lx){
return neutral;
}
if(l <= lx && rx <= r){
return t[x];
}
push(x);
int mx = (lx + rx) >> 1;
return merge(get(x << 1, lx, mx, l, r), get(x << 1 | 1, mx + 1, rx, l, r));
}
// lessen
void build(vector<int> &a){
int sz = len(a);
init(sz);
build(a, 1, 0, n - 1);
}
void upd(int l, int r, int val){
upd(1, 0, n - 1, l, r, val);
}
Node get(int l, int r){
return get(1, 0, n - 1, l, r);
}
ll mn(){
return t[1].mn;
}
};
vector<long long> minimum_costs(vector<int> h, vector<int> L,
vector<int> R) {
int n = len(h);
int q = len(L);
vector<ll> res(q, infl);
vector<int> lef(n), rig(n);
vector<int> st;
for(int i = 0; i < n; i ++){
while(!st.empty() && h[st.back()] <= h[i]){
st.pop_back();
}
if(st.empty()) lef[i] = -1;
else lef[i] = st.back();
st.push_back(i);
}
st.clear();
for(int i = n - 1; i >= 0; i --){
while(!st.empty() && h[st.back()] <= h[i]){
st.pop_back();
}
if(st.empty()) rig[i] = n;
else rig[i] = st.back();
st.push_back(i);
}
SegmentTree t;
t.init(n);
vector<int> ind(q);
iota(all(ind), 0);
int block = sqrt(n);
sort(all(ind), [&](int i, int j){
if((L[i] + 1) / block == (L[j] + 1) / block){
if(R[i] == R[j]) return L[i] < L[j];
return R[i] < R[j];
}
return (L[i] + 1) / block < (L[j] + 1) / block;
});
int curl = 0, curr = -1;
auto del = [&](int i){
int l = lef[i], r = rig[i];
t.upd(l + 1, r - 1, -h[i]);
while(l >= 0){
t.upd(lef[l] + 1, l, -h[l]);
l = lef[l];
}
while(r < n){
t.upd(r, rig[r] - 1, -h[r]);
r = rig[r];
}
};
auto add = [&](int i){
int l = lef[i], r = rig[i];
//cout << i << ' ' << l << ' ' << r << endl;
t.upd(l + 1, r - 1, h[i]);
while(l >= 0){
t.upd(lef[l] + 1, l, h[l]);
l = lef[l];
}
while(r < n){
t.upd(r, rig[r] - 1, h[r]);
r = rig[r];
}
};
auto make = [&](int l, int r)->void{
while(curl < l){
del(curl);
curl ++;
}
while(curl > l){
curl --;
add(curl);
}
while(curr < r){
//cout << curr << endl;
curr ++;
add(curr);
}
while(curr > r){
del(curr);
curr --;
}
};
for(auto u : ind){
//cout << L[u] << ' ' << R[u] << endl;
make(L[u], R[u]);
res[u] = t.mn();
}
return res;
}
