#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[100002];
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;
}
}
};
struct seg1{
int dd, ht;
ll maximo;
int mid;
seg1 *L, *R;
seg1(int l, int r){
dd = l;
ht = r;
mid = (dd + ht)/2;
maximo = -1;
if(l!=r){
L = new seg1(l, mid);
R = new seg1(mid+1, r);
if(L->maximo > R->maximo){
maximo = L->maximo;
}else{
maximo = R->maximo;
}
}else{
maximo = -1;
}
}
void update(int pos, ll cuanto){
if(dd == ht)maximo = max(maximo, cuanto);
else if(pos <= mid)L->update(pos, cuanto);
else R->update(pos, cuanto);
if(dd != ht)maximo = max(L->maximo, R->maximo);
}
ll query(int l, int r){
if( dd == l and r == ht){
return maximo;
}
if( r <= mid ) return L->query(l, r);
if( mid < l) return R->query(l, r);
return max(L->query(l, mid), R->query(mid+1, r));
}
};
struct segDp{
int dd, ht;
ll minimo;
int mid;
segDp *L, *R;
segDp(int l, int r){
dd = l;
ht = r;
mid = (dd + ht)/2;
minimo = -1;
if(l!=r){
L = new segDp(l, mid);
R = new segDp(mid+1, r);
if(L->minimo < R->minimo){
minimo = L->minimo;
}else{
minimo = R->minimo;
}
}else{
minimo = dp[l][0] + dp[l][1] - height[l];
}
}
void update(int pos, ll cuanto){
if(dd == ht)minimo = min(minimo, cuanto);
else if(pos <= mid)L->update(pos, cuanto);
else R->update(pos, cuanto);
if(dd != ht)minimo = max(L->minimo, R->minimo);
}
ll query(int l, int r){
if( dd == l and r == ht){
return minimo;
}
if( r <= mid ) return L->query(l, r);
if( mid < l) return R->query(l, r);
return min(L->query(l, mid), R->query(mid+1, r));
}
};
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.
bool all2 = true;
vector<ll>C;
for(int i = 0 ; i < n ; i ++)if(H[i] != 1 and H[i] != 2)all2 = false;
if(!all2){
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);
segDp *Sdp = new segDp(0, n-1);
/*
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);
}
* */
for(int i = 0 ; i <= n ; i ++){
if(nxtGrande[i] == -1)nxtGrande[i] = INT_MAX;
}
//for(int i = 0 ; i < n ; i ++)cout << dp[i][0] + dp[i][1] - height[i] << " " ;
for(int query = 0 ; query < q; query ++){
ll minimum = LLONG_MAX;
ll maxIzq = H[L[query]];
ll posMaxIzq = L[query];
//cout << "q = " << query << endl;
ll k, s;
k = st->query(L[query], R[query]).ff;
for(ll i = L[query] ; i <= R[query] ;){
bool finish = false;
//cout << "i = " << i << endl;
s = posMaxIzq;
//cout << s << " " << k << endl;
//cout << nxtGrande[i] << " o " << k+1 << endl;
ll siguientePos = min(nxtGrande[s], k + 1);
if(siguientePos >= n)finish = true;
siguientePos = min(siguientePos, n);
ll suma = Sdp->query(i, siguientePos-1);
//cout << "seg = " << suma << endl;
suma += -dp[k][derecha] + (R[query]-k+1)*H[k];
suma += -dp[s][izquierda] + (s-L[query]+1)*H[s];
minimum = min(minimum, suma);
/*
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;
*/
if(finish)break;
if(siguientePos == nxtGrande[i]){
maxIzq = H[nxtGrande[i]];
posMaxIzq = nxtGrande[i];
}
if(siguientePos == k + 1){
if(siguientePos <= R[query]){
k = st->query(siguientePos, R[query]).ff;
}
}
i = siguientePos;
}
C.pb(minimum);
}
}else{
seg1 *st = new seg1(0, n-1);
int lleva = 0, desde = -1;
vector<pair<int, int>>conjuntitos;
int pertenece[n+1];
memset(pertenece, -1, sizeof pertenece);
for(int i = 0 ; i < n ; i ++){
if(H[i] == 2 and desde == -1)continue;
if(H[i] == 2){
conjuntitos.pb({desde, i-1});
for(int j = desde ; j <= i-1 ; j ++)pertenece[j] = conjuntitos.size()-1;
desde = -1;
st->update(i-1, lleva);
lleva = 0;
}else{
if(desde == -1){
lleva = 1;
desde = i;
}else lleva ++ ;
}
}
if(desde != -1){
conjuntitos.pb({desde, n-1});
for(int j = desde ; j <= n-1 ; j ++)pertenece[j] = conjuntitos.size()-1;
desde = -1;
st->update(n-1, lleva);
lleva = 0;
}
for(int query = 0 ; query < q ; query ++){
//cout << "q " << query << endl;
ll li = L[query], ls = R[query];
ll total = R[query] - L[query] + 1;
ll a = 0, b = 0;
ll ans = LLONG_MAX;
if(pertenece[li] == pertenece[ls] and pertenece[li] != -1){
ans = min( ans, total);
//cout << "mismo sitio" << endl;
}else {
if(H[li] == 1){
a = conjuntitos[pertenece[li]].ss - L[query] + 1;
li = conjuntitos[pertenece[li]].ss + 1;
}
if(H[ls] == 1){
b = R[query]-conjuntitos[pertenece[ls]].ff + 1;
ls = conjuntitos[pertenece[ls]].ff -1;
}
//cout << "cur " << ans << " a " << a << " b " << b << endl;
ans = min ( ans, (total-a)*2 + a);
ans = min(ans, (total - b)*2 + b);
//cout << "cur " << ans << endl;
if(li <= ls){
ll cu = st->query(li, ls);
//cout << cu << endl;
if(cu != -1) ans = min (ans, (total - cu)*2 + cu);
else{
ans = min(ans, total*2);
}
}
}
C.pb(ans);
}
}
return C;
}
