#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"
const int SQRT = 140;
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;
}
};
std::vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int n = H.size();
int q = L.size();
vector<long long> cost(n);
auto add = [&](int x,int offset){
int maxi = H[x];
for(int i=x;i>=0;i--){
maxi = max(maxi,H[i]);
cost[i]+=offset*maxi;
}
maxi = H[x];
for(int i=x+1;i<n;i++){
maxi = max(maxi,H[i]);
cost[i]+=offset*maxi;
}
};
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] = INT64_MAX;
for(int i=tarL;i<=tarR;i++)ans[idx]=min(ans[idx],cost[i]);
}
return ans;
}
