#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 75e4;
const ll INF = 1e18;
int N, Q;
ll A[MAXN+10];
pii B[MAXN+10];
ll ans[MAXN+10], ans1[MAXN+10], ans2[MAXN+10];
struct SEG
{
pll tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]={A[tl], tl};
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
pll query(int node, int tl, int tr, int l, int r)
{
if(r<tl || tr<l) return pll(0, 0);
if(l<=tl && tr<=r) return tree[node];
int mid=tl+tr>>1;
return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
}seg;
struct LiChao
{
pll tree[MAXN*4+10];
ll lazy[MAXN*4+10];
void init(int node, int tl, int tr)
{
tree[node]=pll(0, INF);
lazy[node]=0;
if(tl==tr) return;
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
}
void busy(int node, int tl, int tr)
{
tree[node].second+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
ll query(int node, int tl, int tr, int x)
{
busy(node, tl, tr);
ll ret=tree[node].first*x+tree[node].second;
if(tl==tr) return ret;
int mid=tl+tr>>1;
if(x<=mid) ret=min(ret, query(node*2, tl, mid, x));
else ret=min(ret, query(node*2+1, mid+1, tr, x));
return ret;
}
void update(int node, int tl, int tr, int l, int r, ll k)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
}
void update2(int node, int tl, int tr, pll p)
{
busy(node, tl, tr);
ll fl=tree[node].first*tl+tree[node].second, fr=tree[node].first*tr+tree[node].second;
ll nfl=p.first*tl+p.second, nfr=p.first*tr+p.second;
if(fl<=nfl && fr<=nfr) return;
if(nfl<=fl && nfr<=fr) { tree[node]=p; return; }
int mid=tl+tr>>1;
update2(node*2, tl, mid, p);
update2(node*2+1, mid+1, tr, p);
}
void update1(int node, int tl, int tr, int l, int r, pll p)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
update2(node, tl, tr, p);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update1(node*2, tl, mid, l, r, p);
update1(node*2+1, mid+1, tr, l, r, p);
}
}lct1, lct2;
vector<pii> LV[MAXN+10], RV[MAXN+10];
void solve(int l, int r)
{
if(l>r) return;
pll t=seg.query(1, 1, N, l, r);
int mid=t.second;
solve(l, mid-1);
solve(mid+1, r);
ll val;
if(l<=mid-1) val=lct1.query(1, 1, N, mid-1)+A[mid];
else val=A[mid];
lct1.update1(1, 1, N, mid, mid, pll(0, val));
lct1.update(1, 1, N, mid+1, r, A[mid]*(mid-l+1));
lct1.update1(1, 1, N, mid+1, r, pll(A[mid], -A[mid]*mid+val));
if(mid+1<=r) val=lct2.query(1, 1, N, mid+1)+A[mid];
else val=A[mid];
lct2.update1(1, 1, N, mid, mid, pll(0, val));
lct2.update(1, 1, N, l, mid-1, A[mid]*(r-mid+1));
lct2.update1(1, 1, N, l, mid-1, pll(-A[mid], A[mid]*mid+val));
while(!LV[l].empty() && LV[l].back().first<=r)
{
int t=LV[l].back().second;
ans1[t]=lct1.query(1, 1, N, LV[l].back().first);
LV[l].pop_back();
}
while(!RV[r].empty() && RV[r].back().first>=l)
{
int t=RV[r].back().second;
ans2[t]=lct2.query(1, 1, N, RV[r].back().first);
RV[r].pop_back();
}
//printf("solve %d %d\n", l, r);
//for(int i=l; i<=r; i++) printf("%lld ", lct1.query(1, 1, N, i)); printf("\n");
//for(int i=l; i<=r; i++) printf("%lld ", lct2.query(1, 1, N, i)); printf("\n");
}
vector<ll> ret;
vector<ll> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R)
{
N=_H.size(); Q=_L.size();
for(int i=1; i<=N; i++) A[i]=_H[i-1];
for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1};
seg.init(1, 1, N);
for(int i=1; i<=Q; i++)
{
auto [l, r] = B[i];
ans[i]=INF;
int t=seg.query(1, 1, N, l, r).second;
if(l==r) ans[i]=A[l];
if(t+1<=r) LV[t+1].push_back({r, i});
if(l<=t-1) RV[t-1].push_back({l, i});
}
for(int i=1; i<=N; i++)
{
sort(LV[i].begin(), LV[i].end(), greater<pii>());
sort(RV[i].begin(), RV[i].end());
//for(auto it : LV[i]) printf("%d %d / ", it.first, it.second); printf(" : %d\n", i);
//for(auto it : RV[i]) printf("%d %d / ", it.first, it.second); printf(" : %d\n", i);
}
lct1.init(1, 1, N); lct2.init(1, 1, N);
solve(1, N);
for(int i=1; i<=Q; i++)
{
auto [l, r] = B[i];
int t=seg.query(1, 1, N, l, r).second;
ans[i]=min(ans[i], ans1[i]+(t-l+1)*A[t]);
ans[i]=min(ans[i], ans2[i]+(r-t+1)*A[t]);
}
for(int i=1; i<=Q; i++) ret.push_back(ans[i]);
return ret;
}
