//Se apenas tiver 2 no intervalo, nao esquecer de printar a reposta como 2*(R-L+1)
//Se tiver pelo menos um 1, preciso encontrar o maior bloco de 1 possível (minimizando a quantidade de 2)
//A resposta vai ser igual para todo mundo: (R-L+1 - qtd(1) ) * 2 , então eu quero maximizar a qtd de 1
//Lembrar que o primeiro e o último bloco são especiais e precisam ser tratados com carinho
#include <bits/stdc++.h>
#include "meetings.h"
#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MAXN = 1e5+ 10 ;
const ll inf = 1e17 ;
const int intInf = 1e9+10 ;
using namespace std ;
// --------------------------------
struct bloco
{
int qtd , l , r ;
bloco(int qtd = 0 , int l = 0 , int r = 0 )
: qtd(qtd) , l(l) , r(r) {}
void print() { printf("%d %d %d\n" , qtd , l , r) ; }
} ;
int n , q ;
int h[MAXN] , l[MAXN] , r[MAXN] , bestL[MAXN] , bestR[MAXN] ;
ll ansL[MAXN] , ansR[MAXN] ;
// --------------------------------
vector<ll> minimum_costs( vector<int> H , vector<int>L , vector<int> R )
{
q = L.size() ;
n = H.size() ;
vector<ll> ans ;
lp(i,1,n+1) h[i] = H[i-1] ;
lp(i,1,q+1) l[i] = L[i-1]+1 , r[i] = R[i-1]+1 ;
h[0] = intInf , h[n+1] = intInf ;
lp(i,1,n+1)
{
int curL = i-1 ;
while( h[curL] <= h[i] ) curL = bestL[curL] ;
bestL[i] = curL ;
}
for(int i = n ; i > 0 ; i-- )
{
int curR = i+1 ;
while( h[curR] <= h[i] ) curR = bestR[curR] ;
bestR[i] = curR ;
}
lp(i,1,q+1)
{
int L = l[i] , R = r[i] ;
lp( j , L , R+1 )
{
if( bestL[j] < L )
ansL[j] = 1LL * ( j - L + 1) * h[j] ;
else
ansL[j] = 1LL * ( j - bestL[j] ) * h[j] + ansL[ bestL[j] ] ;
}
for(int j = R ; j >= L ; j-- )
{
if( bestR[j] > R )
ansR[j] = 1LL * ( R - j + 1 ) * h[j] ;
else ansR[j] = 1LL * ( bestR[j] - j ) * h[j] + ansR[ bestR[j] ] ;
}
ll tempAns = inf ;
lp(j,L,R+1)
tempAns = min( tempAns , ( ansL[j] + ansR[j] - h[j] ) ) ;
ans.pb(tempAns) ;
}
return ans ;
}
