#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;
};
struct node
{
node *l;
node *r;
deque<interv> s;
ll lazy;
node()
{
lazy=0;
l=NULL;
r=NULL;
}
};
ll eval(node *me, ll poz)
{
ll st=0;
ll dr=me->s.size();
dr--;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(me->s[mij].st>poz)
{
dr=mij-1;
continue;
}
if(me->s[mij].dr<poz)
{
st=mij+1;
continue;
}
ll val=me->s[mij].a*poz+me->s[mij].b+me->lazy;
return val;
}
}
node* build(ll l,ll r)
{
ll poz=getbest(l,r);
ll hv=v[poz];
node *nod = new node;
if(l<=poz-1)
nod->l=build(l,poz-1);
if(r>=poz+1)
nod->r=build(poz+1,r);
ll valmij=0;
if(nod->l==NULL)
{
valmij=v[poz];
nod->l=new node;
}
else
valmij=eval(nod->l,poz-1)+v[poz];
nod->l->s.push_back({poz,poz,0,valmij-nod->l->lazy});
ll off=hv*(poz-l+1);
if(nod->r==NULL)
{
nod=nod->l;
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;
nod->r->lazy+=off;
while(!nod->r->s.empty())
{
interv a=nod->r->s.front();
ll p=a.dr;
ll val1=valmij+hv*p;
ll val2=a.a*p+a.b+nod->r->lazy;
if(val1<=val2)
{
nod->r->s.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+nod->r->lazy;
if(val1<=val2)
{
j=mij;
st=mij+1;
}
else
dr=mij-1;
}
nod->r->s.pop_front();
a.st=j+1;
nod->r->s.push_front(a);
interv add={poz+1,j,hv,valmij-nod->r->lazy};
if(add.st<=add.dr)
nod->r->s.push_front(add);
break;
}
}
if(nod->r->s.empty())
nod->r->s.push_back({poz+1,r,hv,valmij-nod->r->lazy});
node *rez;
if(nod->l->s.size()<nod->r->s.size())
{
ll dif=nod->r->lazy-nod->l->lazy;
rez=nod->r;
while(!nod->l->s.empty())
{
interv a=nod->l->s.back();
nod->l->s.pop_back();
a.b-=dif;
rez->s.push_front(a);
}
}
else
{
ll dif=nod->l->lazy-nod->r->lazy;
rez=nod->l;
while(!nod->r->s.empty())
{
interv a=nod->r->s.front();
nod->r->s.pop_front();
a.b-=dif;
rez->s.push_back(a);
}
}
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);
}
}
/*if(iteration==2)
{
cout<<l<<' '<<r<<' '<<rez->lazy<<'\n';
for(auto i:rez->s)
cout<<i.st<<' '<<i.dr<<' '<<i.a<<' '<<i.b<<'\n';
cout<<'\n';
}*/
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);
}
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);
}
build(1,n);
return sol;
}
