#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const ll INF=1e9;
typedef pair<ll,ll> pll;
ll n,q,v[100005],rmq[21][100005],loga[100005];
ll sdist[5005][5005];
int nxtL[100005],nxtR[100005],cL[21][100005],cR[21][100005],w[100005];
ll getmax(ll l,ll r)
{
ll lg=loga[r-l+1];
return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
ll getmin(ll l,ll r)
{
ll lg=loga[r-l+1];
return min(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
bool inside(int l,int r)
{
return l>=1&&l<=n&&r>=1&&r<=n&&l<=r;
}
ll nrsecv=0;
struct date
{
int l,r;
} secv[100005],mylft[100005][21],myrgt[100005][21];
set<pll> setik;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
n=H.size();
vector<ll> sol;
q=L.size();
ll hmax=0;
for(int i=1;i<=n;i++)
{
v[i]=H[i-1];
hmax=max(hmax,v[i]);
for(int bit=0;bit<=20;bit++)
if((1<<bit)<=i)
loga[i]=bit;
}
if(n<=5000&&q<=5000)
{
for(int i=n;i>=1;i--)
{
rmq[0][i]=v[i];
for(int j=1;j<=20;j++)
{
rmq[j][i]=rmq[j-1][i];
int poz=i+(1<<(j-1));
if(poz<=n)
rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ll st=min(i,j);
ll dr=max(i,j);
ll val=getmax(st,dr);
sdist[i][j]=sdist[i][j-1]+val;
}
}
for(int z=0;z<q;z++)
{
int l=L[z]+1;
int r=R[z]+1;
ll ans=1e18;
for(int i=l;i<=r;i++)
ans=min(ans,sdist[i][r]-sdist[i][l-1]);
sol.push_back(ans);
}
return sol;
}
for(int i=0;i<q;i++)
sol.push_back((int)1e9);
deque<int> coada;
for(int i=1;i<=n;i++)
{
while(!coada.empty()&&v[coada.back()]<=v[i])
coada.pop_back();
if(coada.empty())
nxtL[i]=0;
else
nxtL[i]=coada.back();
coada.push_back(i);
}
coada.clear();
for(int i=n;i>=1;i--)
{
while(!coada.empty()&&v[coada.back()]<=v[i])
coada.pop_back();
if(coada.empty())
nxtR[i]=n+1;
else
nxtR[i]=coada.back();
coada.push_back(i);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=hmax;j++)
cL[j][i]=cR[j][i]=1e9;
ll sum=0;
ll poz=i;
while(poz!=0)
{
ll val=v[poz];
ll last=nxtL[poz];
ll cst=-(n-poz)*val+sum;
cL[val][i]=cst;
sum+=val*abs(poz-last);
poz=last;
}
sum=0;
poz=i;
while(poz<=n)
{
ll val=v[poz];
ll last=nxtR[poz];
ll cst=-(poz-1)*val+sum-v[i];
cR[val][i]=cst;
sum+=val*abs(poz-last);
poz=last;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=hmax;j++)
{
mylft[i][j]={-1,-1};
myrgt[i][j]={-1,-1};
}
int poz=i;
while(poz<=n)
{
int val=v[poz];
int last=nxtR[poz];
mylft[i][val]={poz,last-1};
poz=last;
}
poz=i;
while(poz>=1)
{
int val=v[poz];
int last=nxtL[poz];
myrgt[i][val]={last+1,poz};
poz=last;
}
}
for(ll xL=1;xL<=hmax;xL++)
for(ll xR=1;xR<=hmax;xR++)
{
for(int i=1;i<=n;i++)
w[i]=cL[xL][i]+cR[xR][i];
for(int i=n;i>=1;i--)
{
rmq[0][i]=w[i];
for(int j=1;j<=17;j++)
{
rmq[j][i]=rmq[j-1][i];
int poz=i+(1<<(j-1));
if(poz<=n)
rmq[j][i]=min(rmq[j][i],rmq[j-1][poz]);
}
}
for(int z=0;z<q;z++)
{
int l=L[z]+1;
int r=R[z]+1;
bool ok=0;
if(xL==4&&xR==3)
ok=1;
int l1=mylft[l][xL].l;
int r1=mylft[l][xL].r;
int l2=myrgt[r][xR].l;
int r2=myrgt[r][xR].r;
if(inside(l1,r1)&&inside(l2,r2))
{
l1=max(l1,l2);
r1=min(r1,r2);
if(inside(l1,r1))
{
int val=getmin(l1,r1)+(n-l+1)*xL+r*xR;
sol[z]=min(sol[z],1LL*val);
}
}
}
}
return sol;
}
