#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ss second
#define ff first
#define izquierda 0
#define derecha 1
using namespace std;
ll n, q;
ll nxtGrande[100001];
ll anteriorGrande[100001];
ll dp[100001][2];
vector<int>height;
struct segTree{
int dd, ht;
ll maximo;
ll donde;
int mid;
segTree *L, *R;
segTree(int l, int r){
dd = l;
ht = r;
mid = (dd + ht)/2;
maximo = -1;
donde = 0;
if(l!=r){
L = new segTree(l, mid);
R = new segTree(mid+1, r);
if(L->maximo > R->maximo){
maximo = L->maximo;
donde = L->donde;
}else{
maximo = R->maximo;
donde = R->donde;
}
}else{
maximo = height[l];
donde = l;
}
}
ll getMax(int l , int r){
if( dd == l and r == ht){
return maximo;
}
if( r <= mid ) return L->getMax(l, r);
if( mid < l) return R->getMax(l, r);
return max(L->getMax(l, mid), R->getMax(mid+1, r));
}
pair<ll, ll> query(int l, int r){
if( dd == l and r == ht){
return {donde, maximo};
}
if( r <= mid ) return L->query(l, r);
if( mid < l) return R->query(l, r);
pair<ll, ll> a = L->query(l, mid);
pair<ll, ll> b = R->query(mid+1, r);
if(a.ss > b.ss){
return a;
}else{
return b;
}
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
q = L.size();
n = H.size();
height = H;
set<pair<ll, int> >alturas; // alturas y indices.
for(int i = n-1 ; i >= 0 ; i --){
auto sig = alturas.upper_bound({H[i], n});
if(sig == alturas.end())nxtGrande[i] = -1;
else{
nxtGrande[i] = (*sig).ss;
}
vector<pair<ll, int>>toE;
for(auto j : alturas){
if(j.ff > H[i])break;
toE.pb(j);
}
for(auto j : toE)alturas.erase(j);
alturas.insert({H[i], i});
}
alturas.clear();
for(int i = 0 ; i < n ; i ++){
auto sig = alturas.upper_bound({H[i], n});
if(sig == alturas.end())anteriorGrande[i] = -1;
else anteriorGrande[i] = (*sig).ss;
vector<pair<ll, int>>toE;
for(auto j : alturas){
if(j.ff > H[i])break;
toE.pb(j);
}
for(auto j : toE)alturas.erase(j);
alturas.insert({H[i], i});
}
//for(int i = 0 ; i < n ; i++)cout << anteriorGrande[i] << " " ;
//for(int i = 0 ; i < n ; i ++)cout << nxtGrande[i] << " ";
for(ll i = n-1 ; i >= 0 ; i --){
int sig = nxtGrande[i];
if(sig == -1)dp[i][derecha] = (n-i)*H[i];
else{
dp[i][derecha] = (sig-i)*H[i] + dp[sig][derecha];
}
}
for(ll i = 0 ; i < n ; i ++){
int sig = anteriorGrande[i];
if(sig == -1)dp[i][izquierda] = (i+1)*H[i];
else{
dp[i][izquierda] = (i-sig)*H[i] + dp[sig][izquierda];
}
}
//for(int i = 0 ; i < n ; i ++)cout << dp[i][derecha] << " " ;
//for(int i = 0 ; i < n ; i ++)cout << dp[i][izquierda] << " " ;
segTree *st = new segTree(0, n-1);
vector<ll>C;
for(int query = 0 ; query < q; query ++){
ll minimum = LLONG_MAX;
//cout << "q = " << query << endl;
for(int i = L[query] ; i <= R[query] ; i ++){
ll k = st->query(i, R[query]).ff;
ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k];
k = st->query(L[query], i).ff;
ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k];
minimum = min(minimum, der + izq - H[i]);
//cout << i << " " << izq << " + " << der << endl;
}
C.pb(minimum);
}
return C;
}
