#include<bits/stdc++.h>
#include "meetings.h"
#define fi first
#define se second
using namespace std;
const int NN=75e4;
const int PP=11e5;
const long long INF=(long long)1e18+7;
struct Maxtree
{
int pot;
long long t[2*PP+10];
void init(int n)
{
for(pot=1;pot<n;pot*=2);
for(int i=1;i<=2*pot;i++)
t[i]=-INF;
return;
}
void leaf(int a,long long b)
{
t[pot+a-1]=b;
return;
}
void build()
{
for(int i=pot-1;i>=1;i--)
t[i]=max(t[2*i],t[2*i+1]);
return;
}
long long read(int l,int r)
{
long long ans=-INF;
for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
{
if(l%2==1)
ans=max(ans,t[l++]);
if(r%2==0)
ans=max(ans,t[r--]);
}
return ans;
}
};
struct Tree
{
int pot;
pair<long long,long long> t[2*PP+10];
long long ad[2*PP+10];
bool has_i[2*PP+10];
int s[2*PP+10];
void init(int n)
{
for(pot=1;pot<n;pot*=2);
for(int i=1;i<=2*pot;i++)
{
t[i]={0,0};
ad[i]=0;
has_i[i]=false;
}
for(int i=pot;i<2*pot;i++)
s[i]=1;
for(int i=pot-1;i>0;i--)
s[i]=s[2*i]+s[2*i+1];
return;
}
void push_down(int i)
{
if(has_i[i])
{
ad[2*i]=ad[2*i+1]=0;
has_i[2*i]=has_i[2*i+1]=true;
t[2*i]=t[i];
t[2*i+1]={t[i].fi+t[i].se*s[2*i],t[i].se};
}
ad[2*i]+=ad[i];
ad[2*i+1]+=ad[i];
ad[i]=0;
has_i[i]=false;
return;
}
void upd(int i,int l,int r,int ls,int rs,long long a,long long b)
{
if(ls<=l && r<=rs)
{
ad[i]=0;
t[i]={a+b*(l-ls),b};
has_i[i]=true;
return;
}
push_down(i);
int mid=(l+r)/2;
if(ls<=mid)
upd(2*i,l,mid,ls,rs,a,b);
if(mid+1<=rs)
upd(2*i+1,mid+1,r,ls,rs,a,b);
return;
}
void add(int i,int l,int r,int ls,int rs,long long c)
{
if(ls<=l && r<=rs)
{
ad[i]+=c;
return;
}
push_down(i);
int mid=(l+r)/2;
if(ls<=mid)
add(2*i,l,mid,ls,rs,c);
if(mid+1<=rs)
add(2*i+1,mid+1,r,ls,rs,c);
return;
}
long long read(int x)
{
for(int i=1,l=1,r=pot;l<r;)
{
push_down(i);
int mid=(l+r)/2;
if(x<=mid)
{
i=2*i;
r=mid;
}
else
{
i=2*i+1;
l=mid+1;
}
}
return t[x+pot-1].fi+ad[x+pot-1];
}
};
struct Que
{
int l,r,id,mxh;
bool operator<(const Que &oth)
{
return mxh<oth.mxh;
}
};
Maxtree mxt;
Tree pref,suf;
vector<long long> que_ans;
set<pair<int,int>> st;
pair<int,int> un(pair<int,int> a,pair<int,int> b,long long h)
{
if(a.fi==a.se || b.fi==b.se)
return make_pair(a.fi,b.se);
//cerr<<"("<<a.fi<<","<<a.se<<") ("<<b.fi<<","<<b.se<<")\n";
long long x,y,z;
int bg,en;
// b prefix
x=pref.read(a.se-1)+h;
y=h;
z=h*(a.se-a.fi);
bg=b.fi;en=b.se;
while(bg<en) // first where z better than xy
{
int mid=(bg+en)/2;
if(z+pref.read(mid)<=x+y*(mid-b.fi))
en=mid;
else
bg=mid+1;
}
pref.upd(1,1,pref.pot,b.fi,bg-1,x,y);
pref.add(1,1,pref.pot,bg,b.se-1,z);
// a suffix
x=suf.read(b.fi)+h*(a.se-a.fi);
y=-h;
z=h*(b.se-b.fi);
bg=a.fi;en=a.se;
while(bg<en) // first where xy better than z
{
int mid=(bg+en)/2;
//cerr<<bg<<" "<<en<<" "<<mid<<"\n";
if(z+suf.read(mid)>=x+y*(mid-a.fi))
en=mid;
else
bg=mid+1;
}
suf.upd(1,1,suf.pot,bg,a.se-1,x+y*(bg-a.fi),y);
//cerr<<"s u l="<<bg<<" r="<<a.se-1<<" "<<x+y*(bg-a.fi)<<" "<<y<<"\n";
suf.add(1,1,suf.pot,a.fi,bg-1,z);
//cerr<<"s a l="<<a.fi<<" r="<<bg-1<<" "<<z<<"\n";
return make_pair(a.fi,b.se);
}
void solve(vector<pair<int,int>> &ev,vector<Que> &qq)
{
long long h=ev[0].fi;
vector<pair<int,int>> t;
for(auto v:ev)
{
auto b=st.upper_bound({v.se,NN+10});
auto a=prev(b);
if(t.empty() || t.back()!=(*a))
t.push_back(*a);
t.push_back(*b);
}
//cerr<<"t for h="<<h<<":\n";
//for(auto v:t)
// cerr<<"("<<v.fi<<","<<v.se<<") ";
//cerr<<"\n\n";
mxt.init(t.size());
for(size_t i=0;i<t.size();i++)
{
if(t[i].fi==t[i].se)
mxt.leaf(i+1,0);
else
mxt.leaf(i+1,h*(t[i].se-t[i].fi)-pref.read(t[i].se-1));
}
mxt.build();
for(auto v:qq)
{
que_ans[v.id]=h*(v.r-v.l+1);
int bg,en;
bg=0;en=t.size()-1;
while(bg<en)
{
int mid=(bg+en)/2;
if(t[mid].se<=v.l)
bg=mid+1;
else
en=mid;
}
int a=bg;
bg=0;en=t.size()-1;
while(bg<en)
{
int mid=(bg+en+1)/2;
if(t[mid].fi<=v.r)
bg=mid;
else
en=mid-1;
}
int b=bg;
long long w=max(mxt.read((a+1)+1,(b-1)+1),0LL);
if(t[a].fi<t[a].se && t[a].se-1<=v.r)
{
int x=max(v.l,t[a].fi);
w=max(w,h*(t[a].se-x)-suf.read(x));
//cerr<<"a: "<<x<<" "<<w<<" "<<suf.read(x)<<"\n";
}
if(t[b].fi<t[b].se && v.l<=t[b].fi)
{
int x=min(v.r,t[b].se-1);
w=max(w,h*(x-t[b].fi+1)-pref.read(x));
//cerr<<"b: "<<x<<" "<<w<<"\n";
}
//cerr<<"qid="<<v.id<<" h="<<h<<" que_ans="<<que_ans[v.id]<<" w="<<w<<" a="<<a<<" b="<<b<<"\n";
//cerr<<"t[a]=("<<t[a].fi<<","<<t[a].se<<")\n";
//cerr<<"t[b]=("<<t[b].fi<<","<<t[b].se<<")\n";
//cerr<<"\n";
que_ans[v.id]-=w;
}
for(auto v:t)
st.erase(v);
for(int i=ev.size()-1;i>=0;i--)
{
int v=ev[i].se;
while(v+1<t.back().fi)
{
st.insert(t.back());
t.pop_back();
}
pref.upd(1,1,pref.pot,v,v,h,0);
suf.upd(1,1,suf.pot,v,v,h,0);
auto nw=un({v,v+1},t.back(),h);
t.pop_back();
nw=un(t.back(),nw,h);
t.pop_back();
t.push_back(nw);
}
while(!t.empty())
{
st.insert(t.back());
t.pop_back();
}
return;
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R)
{
int n=H.size();
int q=L.size();
vector<Que> qq(q);
vector<pair<int,int>> ev(n);
pref.init(n);
suf.init(n);
mxt.init(n);
for(int i=0;i<n;i++)
mxt.leaf(i+1,H[i]);
mxt.build();
que_ans.resize(q);
for(int i=0;i<q;i++)
qq[i]={L[i]+1,R[i]+1,i,(int)mxt.read(L[i]+1,R[i]+1)};
sort(qq.begin(),qq.end());
for(int i=0;i<n;i++)
ev[i]={H[i],i+1};
sort(ev.begin(),ev.end());
for(int i=1;i<=n+1;i++)
st.insert({i,i});
vector<pair<int,int>> evtmp;
vector<Que> qqtmp;
for(int i=0,j=0;i<n;i++)
{
evtmp.clear();
qqtmp.clear();
for(;j<q && qq[j].mxh==ev[i].fi;j++)
qqtmp.push_back(qq[j]);
for(;i+1<n && ev[i+1].fi==ev[i].fi;i++)
evtmp.push_back(ev[i]);
evtmp.push_back(ev[i]);
solve(evtmp,qqtmp);
}
return que_ans;
}
