#include <bits/stdc++.h>
#include "meetings.h"
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+1;
const ll inf=1e9;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
struct node{
int mx=0;
vec<int> cntl,cntr;
vec<int>dpl,dpr;
node(){
cntl.assign(21,0);cntr=cntl;
dpl.assign(21,inf);dpr=dpl;
mx=-1;
}
};
node mg(node a,node b){
node c;
c.mx=max(a.mx,b.mx);
vec<int>cost(21,0),pcnt(21,0);
ll sm=0;
for(int i=0;i<=20;i++) pcnt[i]=(i?pcnt[i-1]:0)+b.cntl[i],cost[i]=(i?cost[i-1]:0)+b.cntl[i]*i;
sm=cost[20];
for(int i=0;i<sz(a.dpl);i++){
int x=pcnt[i]*i+a.dpr[i]+sm-cost[i];
int y=pcnt[a.mx]*a.mx+a.dpl[i]+sm-cost[a.mx];
umin(c.dpl[i],y);umin(c.dpr[c.mx],y);
umin(c.dpr[max(i,b.mx)],x);umin(c.dpl[a.mx],x);
}
for(int i=0;i<=20;i++) pcnt[i]=(i?pcnt[i-1]:0)+a.cntr[i],cost[i]=(i?cost[i-1]:0)+a.cntr[i]*i;
sm=cost[20];
for(int i=0;i<sz(b.dpl);i++){
int x=pcnt[i]*i+b.dpl[i]+sm-cost[i];
int y=pcnt[b.mx]*b.mx+b.dpr[i]+sm-cost[b.mx];
umin(c.dpr[i],y);umin(c.dpl[c.mx],y);
umin(c.dpl[max(i,a.mx)],x);umin(c.dpr[b.mx],x);
}
for(int i=0;i<=20;i++){
c.cntr[max(i,b.mx)]+=a.cntr[i];
c.cntr[i]+=b.cntr[i];
c.cntl[max(i,a.mx)]+=b.cntl[i];
c.cntl[i]+=a.cntl[i];
}
return c;
}
node t[4*N];
int a[N];
node emp;
void build(int v,int tl,int tr){
if(tl==tr){
t[v].cntl[a[tl]]=1;
t[v].cntr[a[tl]]=1;
t[v].mx=a[tl];
t[v].dpl[a[tl]]=a[tl];
t[v].dpr[a[tl]]=a[tl];
}
else{
int tm=(tl+tr)>>1;
build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
t[v]=mg(t[v<<1],t[v<<1|1]);
}
}
node get(int l,int r,int v,int tl,int tr){
if(tl>=l&&tr<=r)
return t[v];
if(tl>r||tr<l)
return emp;
int tm=(tl+tr)>>1;
return mg(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
vec<ll> minimum_costs(vec<int> a,vec<int> l,vec<int> r){
int q=sz(l);
vec<ll>ans(q);
int n=sz(a);
for(int i=0;i<n;i++) ::a[i]=a[i];
bool ok=(*max_element(all(a))<=20);
if(ok)
build(1,0,n-1);
vec<int>lft(n),rgt(n);
vec<pii>st;
st.pb({2e9,-1});
for(int i=0;i<n;i++){
while(sz(st) && a[i]>st.back().f){
rgt[st.back().s]=i-1;
st.pop_back();
}
lft[i]=st.back().s+1;
st.pb({a[i],i});
}
while(sz(st)>1) rgt[st.back().s]=n-1,st.pop_back();
const ll infq=1e18;
auto stupid=[&](int l,int r){
int mx=-2e9;
vec<ll> pref(n+1,0);
for(int i=l;i<=r;i++){
int l1=i,r1=min(r,rgt[i]);
ll cst=1ll*a[i]*(i-max(lft[i],l)+1);
pref[l1]+=cst;pref[r1+1]-=cst;
// cout<<"ALO "<<l1<<' '<<r1<<' '<<cst<<endl;
l1=max(l,lft[i]),r1=i;
cst=1ll*a[i]*(min(rgt[i],r)-i+1);
// cout<<"ALO "<<l1<<' '<<r1<<' '<<cst<<endl;
pref[l1]+=cst;pref[r1+1]-=cst;
pref[i]-=a[i];pref[i+1]+=a[i];
}
for(int i=1;i<=n;i++) pref[i]+=pref[i-1];
ll ans=infq;
int j=l;
int j1=l;
for(int i=l;i<=r;i++){
if(a[i]<a[j]) j=i;
if(a[i]>a[j1]) j1=i;
ans=min(ans,pref[i]);
// cerr<<"DBG "<<a[i]<<' '<<pref[i]<<'\n';
}
// cout<<endl;
return ans;
};
for(int i=0;i<q;i++){
if(ok){
ans[i]=inf;
node me=get(l[i],r[i],1,0,n-1);
for(auto &z : me.dpl) umin(ans[i],(ll)z);
for(auto &z : me.dpr) umin(ans[i],(ll)z);
}
else
ans[i]=stupid(l[i],r[i]);
}
return ans;
}
