#include "meetings.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp(x, y) make_pair(x ,y)
using namespace std;
typedef long long ll;
const int N=1<<17;
int ans[N+N], pref[N+N], suf[N+N], siz[N+N];
pair<int, pair<int, int> > quer(int v, int L, int R, int l, int r){
if(L==l && R==r){
//cout<<L<<" "<<R<<" "<<ans[v]<<" "<<pref[v]<<" "<<suf[v]<<" "<<siz[v]<<"\n";
return(mp(ans[v], mp(pref[v], suf[v])));
}
int M=(L+R)>>1;
if(l<=M && M<r){
pair<int, pair<int, int> > a=quer(2*v, L, M, l, M), b=quer(2*v+1, M+1, R, M+1, r);
int x=max({a.st, b.st, a.nd.nd+b.nd.st});
int y=a.nd.st;
int z=b.nd.nd;
if(M-l+1==a.st)y=b.nd.st+a.st;
if(r-M==b.st)z=b.st+a.nd.nd;
//cout<<L<<" "<<R<<" "<<l<<" "<<r<<" | "<<x<<" "<<y<<" "<<z<<"\n";
return mp(x, mp(y, z));
}
else{
if(l<=M)return quer(2*v, L, M, l, r);
else return quer(2*v+1, M+1, R, l, r);
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
std::vector<long long> C(Q);
int n=H.size();
int M=0;
for(int i=0; i<n; i++)M=max(M, H[i]);
if(M<=2){
for(int i=0; i<n; i++){
ans[N+i]=pref[N+i]=suf[N+i]=(H[i]==1);
siz[N+i]=1;
}
for(int i=N-1; i>0; i--){
ans[i]=max({ans[2*i], ans[2*i+1], pref[2*i+1]+suf[2*i]});
pref[i]=pref[2*i];
if(ans[2*i]==siz[2*i])pref[i]=siz[2*i]+pref[2*i+1];
suf[i]=suf[2*i+1];
if(ans[2*i+1]==siz[2*i+1])suf[i]=siz[2*i]+suf[2*i];
siz[i]=siz[2*i]*2;
}
for(int j=0; j<Q; j++){
C[j]=(R[j]-L[j]+1)*2-quer(1, 0, N-1, L[j], R[j]).st;
}
}
else{
vector<long long> lew(n), pra(n);
for (int j = 0; j < Q; ++j) {
lew[L[j]]=H[L[j]];
stack<pair<int, int>> S;
ll ans=0;
for(int i=L[j]; i<=R[j]; i++){
int k=0;
while(S.size() && H[i]>S.top().st){
ans-=S.top().st*1ll*S.top().nd;
k+=S.top().nd;
S.pop();
}
k++;
ans+=H[i]*1ll*k;
S.push(mp(H[i], k));
lew[i]=ans;
}
ans=0;
while(S.size())S.pop();
for(int i=R[j]; i>=L[j]; i--){
int k=0;
while(S.size() && H[i]>S.top().st){
ans-=S.top().st*1ll*S.top().nd;
k+=S.top().nd;
S.pop();
}
k++;
ans+=H[i]*1ll*k;
S.push(mp(H[i], k));
pra[i]=ans;
}
ll res=1e18;
for(int i=L[j]; i<=R[j]; i++){
//cout<<i<<" "<<lew[i]<<" "<<pra[i]<<"\n";
res=min(res, lew[i]+pra[i]-H[i]);
}
C[j] = res;
}
}
return C;
}
