#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int iteration;
ll n,q,v[750005],rmq[21][750005];
ll loga[750005];
vector<ll> sol;
ll best(ll i,ll j)
{
if(v[i]>v[j])
return i;
if(v[j]>v[i])
return j;
if(iteration==1)
return max(i,j);
else
return min(i,j);
}
ll getbest(ll l,ll r)
{
ll lg=loga[r-l+1];
return best(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
struct query
{
ll r,ind,cst;
};
vector<query> who[750005];
struct interv
{
ll st,dr,a,b;
};
vector<deque<interv>> s;
vector<ll> lazy;
ll eval(ll me, ll poz)
{
ll st=0;
ll dr=s[me].size();
dr--;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(s[me][mij].st>poz)
{
dr=mij-1;
continue;
}
if(s[me][mij].dr<poz)
{
st=mij+1;
continue;
}
ll val=s[me][mij].a*poz+s[me][mij].b+lazy[me];
return val;
}
}
ll cntnodes=0;
int plsnode()
{
cntnodes++;
if(s.size()<=cntnodes)
{
s.resize(cntnodes+1);
lazy.resize(cntnodes+1);
}
s[cntnodes].clear();
lazy[cntnodes]=0;
return cntnodes;
}
int nrop=0;
int build(int l,int r)
{
ll poz=getbest(l,r);
ll hv=v[poz];
//node *nod = new node;
ll nod=0;
ll nodl=0;
ll nodr=0;
if(l<=poz-1)
nodl=build(l,poz-1);
if(r>=poz+1)
nodr=build(poz+1,r);
ll valmij=0;
if(nodl==0)
{
valmij=v[poz];
nodl=plsnode();
}
else
valmij=eval(nodl,poz-1)+v[poz];
s[nodl].push_back({poz,poz,0,valmij-lazy[nodl]});
ll off=hv*(poz-l+1);
if(nodr==0)
{
nod=nodl;
for(auto i:who[l])
{
ll rgt=i.r;
ll ind=i.ind;
ll cst=i.cst;
if(rgt<=r)
{
ll val=eval(nod,rgt)+cst;
sol[ind]=min(sol[ind],val);
}
}
return nod;
}
valmij-=hv*poz;
lazy[nodr]+=off;
while(!s[nodr].empty())
{
interv a=s[nodr].front();
ll p=a.dr;
ll val1=valmij+hv*p;
ll val2=a.a*p+a.b+lazy[nodr];
if(val1<=val2)
{
s[nodr].pop_front();
continue;
}
else
{
ll st=a.st;
ll dr=a.dr;
ll j=st-1;
while(st<=dr)
{
ll mij=(st+dr)/2;
val1=valmij+hv*mij;
val2=a.a*mij+a.b+lazy[nodr];
if(val1<=val2)
{
j=mij;
st=mij+1;
}
else
dr=mij-1;
}
s[nodr].pop_front();
a.st=j+1;
s[nodr].push_front(a);
interv add={poz+1,j,hv,valmij-lazy[nodr]};
if(add.st<=add.dr)
s[nodr].push_front(add);
break;
}
}
if(s[nodr].empty())
s[nodr].push_back({poz+1,r,hv,valmij-lazy[nodr]});
ll rez=0;
if(s[nodl].size()>s[nodr].size())
{
ll dif=lazy[nodr]-lazy[nodl];
rez=nodr;
while(!s[nodl].empty())
{
interv a=s[nodl].back();
s[nodl].pop_back();
a.b-=dif;
s[rez].push_front(a);
if(iteration==1)
nrop++;
}
}
else
{
ll dif=lazy[nodl]-lazy[nodr];
rez=nodl;
while(!s[nodr].empty())
{
interv a=s[nodr].front();
s[nodr].pop_front();
a.b-=dif;
s[rez].push_back(a);
if(iteration==1)
nrop++;
}
}
for(auto i:who[l])
{
ll rgt=i.r;
ll ind=i.ind;
ll cst=i.cst;
if(rgt<=r)
{
ll val=eval(rez,rgt)+cst;
sol[ind]=min(sol[ind],val);
}
}
return rez;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
n=H.size();
q=L.size();
sol.resize(q);
iteration=1;
for(int i=1;i<=n;i++)
{
v[i]=H[i-1];
for(int bit=0;bit<=20;bit++)
if((1<<bit)<=i)
loga[i]=bit;
}
for(int i=0;i<q;i++)
{
sol[i]=1e17;
L[i]++;
R[i]++;
}
for(int i=n;i>=1;i--)
{
rmq[0][i]=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]=best(rmq[j][i],rmq[j-1][poz]);
}
}
for(int i=0;i<q;i++)
{
ll poz=getbest(L[i],R[i]);
ll cst=(poz-L[i]+1)*v[poz];
if(poz+1<=R[i])
who[poz+1].push_back({R[i],i,cst});
else
sol[i]=min(sol[i],cst);
}
cntnodes=0;
build(1,n);
iteration=2;
reverse(v+1,v+n+1);
for(int i=1;i<=n;i++)
who[i].clear();
for(int i=0;i<q;i++)
{
L[i]=n-L[i]+1;
R[i]=n-R[i]+1;
swap(L[i],R[i]);
}
for(int i=n;i>=1;i--)
{
rmq[0][i]=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]=best(rmq[j][i],rmq[j-1][poz]);
}
}
for(int i=0;i<q;i++)
{
ll lft=L[i];
ll rgt=R[i];
ll poz=getbest(L[i],R[i]);
ll cst=(poz-L[i]+1)*v[poz];
if(poz+1<=R[i])
who[poz+1].push_back({R[i],i,cst});
else
sol[i]=min(sol[i],cst);
}
cntnodes=0;
build(1,n);
return sol;
}
