#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=20,kaf=(1<<lg),maxr=1e6+5;
long long ezaf=0,all[maxn],n,dpl[maxn],dpr[maxn],tr[maxn],tl[maxn],psl[maxn],psr[maxn],inf=1e16,ezafq[maxn];
vector<pair<long long,long long>>allql[maxn],allqr[maxn];
long long q,res[maxn];
struct func{
long long x0,y0,sh,ta,wa;
func(){
x0=0;
y0=inf;
sh=0;
ta=inf;
wa=inf;
}
long long get(long long x){
return (x-x0)*sh+y0;
}
}fakefunc;
struct lichao{
struct node{
func f;
long long cl,cr;
node(){
cl=cr=-1;
}
}fakenode;
vector<node>alln;
long long te=1;
lichao(){
te=1;
alln.resize(1);
}
void clear(){
for(long long i=0;i<te;i++){
alln[i]=fakenode;
}
te=1;
}
long long getl(long long i){
if(alln[i].cl==-1){
if((long long)alln.size()==te){
alln.push_back(fakenode);
}
alln[i].cl=te;
te++;
}
return alln[i].cl;
}
long long getr(long long i){
if(alln[i].cr==-1){
if((long long)alln.size()==te){
alln.push_back(fakenode);
}
alln[i].cr=te;
te++;
}
return alln[i].cr;
}
long long pors(long long i,long long l,long long r,long long x){
if(i==-1){
return inf;
}
long long ret=alln[i].f.get(x);
long long mid=(l+r)>>1;
if(r==l+1){
return ret;
}
if(x<mid){
ret=min(ret,pors(alln[i].cl,l,mid,x));
}else{
ret=min(ret,pors(alln[i].cr,mid,r,x));
}
return ret;
}
void ins(long long i,long long l,long long r,func fa){
if(alln[i].f.sh==0){
swap(alln[i].f,fa);
return ;
}
if(alln[i].f.get(l)>fa.get(l)){
swap(alln[i].f,fa);
}
if(r==l+1){
return ;
}
long long mid=(l+r)>>1;
if(alln[i].f.get(mid)<=fa.get(mid)){
return ins(getr(i),mid,r,fa);
}else{
swap(alln[i].f,fa);
return ins(getl(i),l,mid,fa);
}
}
}lch;
bool cmp(pair<long long,func>a,pair<long long,func>b){
if(a.first!=b.first){
return a.first<b.first;
}
if(a.second.x0!=b.second.x0){
return a.second.x0<b.second.x0;
}
if(a.second.sh!=b.second.sh){
return a.second.sh<b.second.sh;
}
return a.second.y0<b.second.y0;
}
struct segment{
vector<pair<long long,long long>>segq[(1<<(lg+1))];
vector<pair<long long,func>>segi[(1<<(lg+1))];
void clear(){
for(long long i=0;i<(1<<(lg+1));i++){
segq[i].clear();
segi[i].clear();
}
}
void insq(long long i,pair<long long,long long>w){
i+=kaf;
while(i>0){
segq[i].push_back(w);
i>>=1;
}
}
void insi(long long i,long long l,long long r,long long tl,long long tr,pair<long long,func>w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
segi[i].push_back(w);
return ;
}
long long m=(l+r)>>1;
insi((i<<1),l,m,tl,tr,w);
insi((i<<1)^1,m+1,r,tl,tr,w);
return ;
}
void calc(long long w){
lichao lich;
for(long long i=0;i<(1<<(lg+1));i++){
sort(segq[i].begin(),segq[i].end());
sort(segi[i].begin(),segi[i].end(),cmp);
lich.clear();
if(w==0){
long long i1=(long long)segq[i].size()-1,i2=(long long)segi[i].size()-1;
while(i1>=0&&i2>=0){
if(segq[i][i1].first<=segi[i][i2].first){
lich.ins(0,0,maxr-1,segi[i][i2].second);
i2--;
}else{
res[segq[i][i1].first]=min(res[segq[i][i1].first],lich.pors(0,0,maxr,segq[i][i1].second)+ezafq[segq[i][i1].first]);
i1--;
}
}
while(i1>=0){
res[segq[i][i1].first]=min(res[segq[i][i1].first],lich.pors(0,0,maxr,segq[i][i1].second)+ezafq[segq[i][i1].first]);
i1--;
}
}else{
long long i1=0,i2=0;
while(i1<(long long)segq[i].size()&&i2<(long long)segi[i].size()){
if(segq[i][i1].first>=segi[i][i2].first){
lich.ins(0,0,maxr-1,segi[i][i2].second);
i2++;
}else{
res[segq[i][i1].first]=min(res[segq[i][i1].first],lich.pors(0,0,maxr,segq[i][i1].second)+ezafq[segq[i][i1].first]);
i1++;
}
}
while(i1<(long long)segq[i].size()){
res[segq[i][i1].first]=min(res[segq[i][i1].first],lich.pors(0,0,maxr,segq[i][i1].second)+ezafq[segq[i][i1].first]);
i1++;
}
}
}
}
}seg;
void caltltr(){
vector<long long>v;
all[0]=inf;
all[n+1]=inf;
v.push_back(0);
for(long long i=1;i<=n;i++){
while(all[v.back()]<all[i]){
v.pop_back();
}
tl[i]=v.back();
v.push_back(i);
}
v.clear();
v.push_back(n+1);
for(long long i=n;i>=1;i--){
while(all[v.back()]<all[i]){
v.pop_back();
}
tr[i]=v.back();
v.push_back(i);
}
}
void solvel(){
vector<long long>v;
v.push_back(0);
for(long long i=1;i<=n;i++){
dpl[i]=inf;
while(all[v.back()]<=all[i]){
dpl[i]=min(dpl[i],dpl[v.back()]+(i-v.back()-1)*all[v.back()]);
v.pop_back();
}
v.push_back(i);
if(tl[i]==i-1){
dpl[i]=psl[i]=psl[tl[i]]+all[i];
}else{
dpl[i]+=all[i];
}
psl[i]=psl[tl[i]]+(i-tl[i])*all[i];
func fa;
fa.x0=i;
fa.y0=dpl[i];
fa.sh=all[i];
seg.insi(1,0,kaf-1,i,tr[i]-1,make_pair(i,fa));
for(auto x:allqr[i]){
long long p=lower_bound(v.begin(),v.end(),x.first)-v.begin();
long long now=i;
now=v[p];
long long manf=psl[tl[now]]+(x.first-1-tl[now])*all[now];
ezafq[x.second]=manf;
seg.insq(i,x);
//res[x.second]=min(res[x.second],seg.pors(1,0,kaf-1,p+1,(long long)v.size()-1,i)-manf);
}
}
seg.calc(0);
}
void solver(){
vector<long long>v;
deque<long long>tofv;
seg.clear();
v.push_back(n+1);
tofv.push_front(n+1);
for(long long i=n;i>=1;i--){
dpr[i]=inf;
while(all[v.back()]<all[i]){
dpr[i]=min(dpr[i],dpr[v.back()]+(v.back()-i-1)*all[v.back()]);
v.pop_back();
tofv.pop_front();
}
tofv.push_front(i);
v.push_back(i);
if(tr[i]==i+1){
dpr[i]=psr[i]=psr[tr[i]]+all[i];
}else{
dpr[i]+=all[i];
}
psr[i]=psr[tr[i]]+(tr[i]-i)*all[i];
func fa;
fa.x0=i;
fa.y0=dpl[i];
fa.sh=-all[i];
//seg.ins(v.size()-1,fa);
for(auto x:allql[i]){
long long p=lower_bound(tofv.begin(),tofv.end(),x.first+1)-tofv.begin();
long long now=i;
if(p==0||p-1>=(long long)tofv.size()){
return ;
}
now=tofv[p-1];
long long manf=psr[tr[now]]+(tr[now]-x.first-1)*all[now];
now=i;
while(tr[now]<=x.first){
res[x.second]=min(res[x.second],dpr[now]+(now-i)*all[now]-manf);
now=tr[now];
}
}
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
n=H.size();
for(long long i=1;i<=n;i++){
all[i]=H[i-1];
}
q=(long long)L.size();
for(long long i=0;i<q;i++){
L[i]++;
R[i]++;
res[i]=inf;
allql[L[i]].push_back(make_pair(R[i],i));
allqr[R[i]].push_back(make_pair(L[i],i));
}
caltltr();
solvel();
solver();
vector<long long>ret;
for(long long i=0;i<q;i++){
if(L[i]==R[i]){
res[i]=all[L[i]];
}
ret.push_back(res[i]);
}
return ret;
}
