#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"
const int SQRT = 100;
struct Query{
int L,R,idx;
Query(int L,int R,int idx):L(L),R(R),idx(idx){}
bool operator<(const Query& other)const{
return L/SQRT == other.L/SQRT ? R<other.R : L<other.L;
}
};
struct Segtree{ // Range add, range min
vector<long long> tree,lazy;
int N;
Segtree(int N):tree(4*N),lazy(4*N),N(N){}
void update(int qL,int qR,int qX,int x,int L,int R){
if(lazy[x]){
tree[x]+=lazy[x];
if(L!=R){
lazy[2*x]+=lazy[x];
lazy[2*x+1]+=lazy[x];
}
lazy[x]=0;
}
if(qR<L or R<qL)return;
if(qL<=L and R<=qR){
tree[x]+=qX;
if(L!=R){
lazy[2*x]+=qX;
lazy[2*x+1]+=qX;
}
return;
}
int mid = (L+R)/2;
update(qL,qR,qX,2*x,L,mid);
update(qL,qR,qX,2*x+1,mid+1,R);
tree[x] = min(tree[2*x],tree[2*x+1]);
}
void update(int qL,int qR,int qX){
update(qL,qR,qX,1,0,N-1);
}
long long get(int qL,int qR,int x,int L,int R){
if(lazy[x]){
tree[x]+=lazy[x];
if(L!=R){
lazy[2*x]+=lazy[x];
lazy[2*x+1]+=lazy[x];
}
lazy[x]=0;
}
if(qR<L or R<qL)return INT64_MAX;
if(qL<=L and R<=qR)return tree[x];
int mid = (L+R)/2;
return min(get(qL,qR,2*x,L,mid),get(qL,qR,2*x+1,mid+1,R));
}
long long get(int qL,int qR){return get(qL,qR,1,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();
Segtree cost(n);
vector<stack<pair<int,int>>> fromleft(n);
vector<stack<pair<int,int>>> fromright(n);
{
// from left calculation
stack<pair<int,int>> s;
s.emplace(INT32_MAX,-1);
for(int i=0;i<n;i++){
while(s.top().first<=H[i])s.pop();
s.emplace(H[i],i);
fromleft[i] = s;
}
}
{
// from right calculation
stack<pair<int,int>> s;
s.emplace(INT32_MAX,n);
for(int i=n-1;i>=0;i--){
while(s.top().first<=H[i])s.pop();
s.emplace(H[i],i);
fromright[i] = s;
}
}
auto add = [&](int x,int offset){
{
// from left calculation
stack<pair<int,int>> s = fromleft[x];
while(s.size()>1){
auto [curr,idx] = s.top();s.pop();
cost.update(s.top().second+1,idx,curr*offset);
}
}
{
// from right calculation
stack<pair<int,int>> s = fromright[x];
s.top().second++;
while(s.size()>1){
auto [curr,idx] = s.top();s.pop();
cost.update(idx,s.top().second-1,curr*offset);
}
}
};
int l = 0;
int r = -1;
vector<long long> ans(q);
vector<Query> queries;
for(int i=0;i<q;i++)queries.emplace_back(L[i],R[i],i);
sort(queries.begin(),queries.end());
for(auto[tarL,tarR,idx]:queries){
while(l<tarL)add(l++,-1);
while(tarL<l)add(--l,1);
while(r<tarR)add(++r,1);
while(tarR<r)add(r--,-1);
ans[idx] = cost.get(tarL,tarR);
}
return ans;
}
