#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=75e4+7;
vector<pair<pair<int,int>,int>>V[LIM];
pair<ll,ll>tr[4*LIM][2], pytanie[4*LIM], T[LIM], zle={-1, -1};
set<pair<int,int>>S;
ll dodaj[4*LIM][2], ile[4*LIM], N=1;
void spl(int v, int k) {
if(tr[v][k]!=zle) {
tr[2*v][k]=tr[v][k];
tr[2*v+1][k]={tr[v][k].st+ile[2*v]*tr[v][k].nd, tr[v][k].nd};
tr[v][k]=zle;
dodaj[2*v][k]=0;
dodaj[2*v+1][k]=0;
}
if(dodaj[v][k]) {
if(tr[2*v][k]!=zle) tr[2*v][k].st+=dodaj[v][k];
else dodaj[2*v][k]+=dodaj[v][k];
if(tr[2*v+1][k]!=zle) tr[2*v+1][k].st+=dodaj[v][k];
else dodaj[2*v+1][k]+=dodaj[v][k];
dodaj[v][k]=0;
}
}
void updd(int v, int l, int r, int a, int b, ll x, int k) {
if(r<a || l>b) return;
if(a<=l && r<=b) {
if(tr[v][k]==zle) dodaj[v][k]+=x;
else tr[v][k].st+=x;
return;
}
spl(v, k);
int mid=(l+r)/2;
updd(2*v, l, mid, a, b, x, k);
updd(2*v+1, mid+1, r, a, b, x, k);
}
void upds(int v, ll l, ll r, int a, int b, ll x, ll y, int k) {
if(r<a || l>b) return;
if(a<=l && r<=b) {
dodaj[v][k]=0;
tr[v][k]={x+y*l, y};
return;
}
spl(v, k);
int mid=(l+r)/2;
upds(2*v, l, mid, a, b, x, y, k);
upds(2*v+1, mid+1, r, a, b, x, y, k);
}
ll pytaj(ll v, int l, int r, int x, int k) {
if(l==r) return tr[v][k].st;
spl(v, k);
int mid=(l+r)/2;
if(x<=mid) return pytaj(2*v, l, mid, x, k);
return pytaj(2*v+1, mid+1, r, x, k);
}
pair<ll,ll>jakie(int l, int r) {
l+=N; r+=N;
pair<ll,ll>ans=max(pytanie[l], pytanie[r]);
while(l/2!=r/2) {
if(l%2==0) ans=max(ans, pytanie[l+1]);
if(r%2==1) ans=max(ans, pytanie[r-1]);
l/=2; r/=2;
}
return ans;
}
vector<ll>minimum_costs(vector<int>H, vector<int>L, vector<int>R) {
int n=H.size();
while(N<=n) N*=2;
rep(i, N) ile[N+i]=1;
for(int i=N-1; i; --i) ile[i]=ile[2*i]+ile[2*i+1];
rep(i, n) {
T[i]={H[i], i};
pytanie[N+i]={H[i], i};
}
for(int i=N-1; i; --i) pytanie[i]=max(pytanie[2*i], pytanie[2*i+1]);
rep(i, L.size()) V[jakie(L[i], R[i]).nd].pb({{L[i], R[i]}, i});
vector<ll>wyniki(L.size());
sort(T, T+n);
S.insert({-LIM, -LIM});
S.insert({LIM, LIM});
rep(i, n) {
for(auto j : V[T[i].nd]) {
wyniki[j.nd]=pytaj(1, 0, N-1, j.st.nd, 0)+(T[i].nd-j.st.st+1)*T[i].st;
wyniki[j.nd]=min(wyniki[j.nd], pytaj(1, 0, N-1, n-j.st.st, 1)+(j.st.nd-T[i].nd+1)*T[i].st);
}
auto it=S.lower_bound({T[i].nd, T[i].nd});
auto prawo=*it; --it;
auto lewo=*it;
pair<ll,ll>lewod={T[i].nd, T[i].nd}, prawod={T[i].nd, T[i].nd};
if(lewo.nd==T[i].nd-1) {
S.erase(lewo);
lewod.st=lewo.st;
}
if(prawo.st==T[i].nd+1) {
S.erase(prawo);
prawod.nd=prawo.nd;
}
updd(1, 0, N-1, prawod.st, prawod.nd, T[i].st*(lewod.nd-lewod.st+1), 0);
// znajduje ostatni element na ktorym dp[T[i].nd-1]+(po-T[i].nd+1)*T[i].st<pytaj(po)
ll dplewo=0, po=prawod.st, ko=prawod.nd;
if(lewod.st!=T[i].nd) dplewo=pytaj(1, 0, N-1, T[i].nd-1, 0);
while(po<ko) {
ll sr=(po+ko+1)/2;
if(dplewo+(sr-T[i].nd+1)*T[i].st<=pytaj(1, 0, N-1, sr, 0)) po=sr; else ko=sr-1;
}
upds(1, 0, N-1, T[i].nd, po, dplewo+(1-T[i].nd)*T[i].st, T[i].st, 0);
updd(1, 0, N-1, n-lewod.nd, n-lewod.st, T[i].st*(prawod.nd-prawod.st+1), 1);
// znajduje pierwszy element na ktorym dpprawo+(T[i].nd-sr+1)*T[i].st<pytaj(sr)
ll dpprawo=0; po=lewod.st; ko=lewod.nd;
if(prawod.st!=prawod.nd) dpprawo=pytaj(1, 0, N-1, n-T[i].nd-1, 1);
while(po<ko) {
ll sr=(po+ko)/2;
if(dpprawo+(T[i].nd-sr+1)*T[i].st<=pytaj(1, 0, N-1, n-sr, 1)) ko=sr; else po=sr+1;
}
upds(1, 0, N-1, n-T[i].nd, n-po, dpprawo+(T[i].nd+1-n)*T[i].st, T[i].st, 1);
S.insert({lewod.st, prawod.nd});
}
return wyniki;
}
