#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) (int)x.size()
const int MAXN=1e5+10;
const ll inf=1e17;
typedef tuple<int,int,int> trio;
typedef pair<int,int> pii;
int n;
ll dp[MAXN],peso[MAXN],seg[4*MAXN],lz[4*MAXN];
vector<ll>v;
set<int> st[23];
void build(int ind,int l,int r){
if(l==r){
seg[ind]=dp[l];
return;
}
int m=(l+r)>>1; build(2*ind,l,m); build(2*ind+1,m+1,r);
seg[ind]=min(seg[2*ind],seg[2*ind+1]);
}
void unlz(int ind,int l,int r){
seg[ind]+=lz[ind];
if(l!=r){
lz[2*ind]+=lz[ind];
lz[2*ind+1]+=lz[ind];
}
lz[ind]=0;
}
void add(int ind,int l,int r,int a,int b,ll val){
unlz(ind,l,r);
if(a>r || l>b) return;
if(a<=l && b>=r){
lz[ind]+=val;
unlz(ind,l,r);
return;
}
int m=(l+r)>>1;
add(2*ind,l,m,a,b,val); add(2*ind+1,m+1,r,a,b,val);
seg[ind]=min(seg[2*ind],seg[2*ind+1]);
}
ll query(int ind,int l,int r,int a,int b){
unlz(ind,l,r);
if(a>r || l>b) return inf;
if(a<=l && b>=r)return seg[ind];
int m=(l+r)>>1;
return min(query(2*ind,l,m,a,b),query(2*ind+1,m+1,r,a,b));
}
void precalc(){
ll cur=0;
stack<int> sta;
fall(i,0,n-1){
peso[i]=1;
cur+=v[i];
while(sz(sta)){
auto x=sta.top();
if(v[x]>v[i]) break;
cur+=peso[x]*(v[i]-v[x]);
sta.pop();
peso[i]+=peso[x];
}
dp[i]=cur;
sta.push(i);
}
while(sz(sta))sta.pop();
cur=0;
rfall(i,n-1,0){
peso[i]=1;
while(sz(sta)){
auto x=sta.top();
if(v[x]>v[i]) break;
cur+=peso[x]*(v[i]-v[x]);
sta.pop();
peso[i]+=peso[x];
}
dp[i]+=cur;
sta.push(i);
cur+=v[i];
}
fall(i,0,n-1)
fall(j,1,v[i]) st[j].insert(i);
build(1,0,n-1);
}
ll quer(int l,int r){
vector<trio> to_rem;
int cur=1;
while(cur<=20){
auto it=st[cur].lower_bound(l);
if(it==st[cur].end() || *it>r) break;
auto x=*it;
ll custo=l*v[x]; int at=v[x]+1;
while(at<=20){
auto it2=st[at].lower_bound(l);
if(it2==st[at].begin()) break;
it2--;
custo+=(*it2+1)*(v[*it2]-at+1);
at=v[*it2]+1;
}
int R=r;
auto it2=st[v[x]+1].upper_bound(x);
if(it2!=st[v[x]+1].end()) R=min(R,*it2-1);
to_rem.pb({x,R,custo});
cur=v[x]+1;
}
cur=1;
while(cur<=20){
auto it=st[cur].upper_bound(r);
if(it==st[cur].begin()) break;
it--;
if(*it<l) break;
auto x=*it;
ll custo=(n-1-r)*v[x]; int at=v[x]+1;
while(at<=20){
auto it2=st[at].upper_bound(r);
if(it2==st[at].end()) break;
custo+=(n-*it2)*(v[*it2]-at+1);
at=v[*it2]+1;
}
int L=l;
auto it2=st[v[x]+1].upper_bound(r);
if(it2!=st[v[x]+1].begin()){
it2--;
L=max(L,*it2+1);
}
to_rem.pb({L,x,custo});
cur=v[x]+1;
}
for(auto [a,b,c]:to_rem) add(1,0,n-1,a,b,-c);
ll ans=query(1,0,n-1,l,r);
for(auto [a,b,c]:to_rem) add(1,0,n-1,a,b,c);
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
n=sz(H);
for(auto u:H) v.pb(u);
precalc();
vector<ll> ans;
fall(i,0,sz(L)-1){
ll x=quer(L[i],R[i]);
ans.pb(x);
}
return ans;
}
