#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
struct Nodo{
long long Segmento, Suma, Izquierda, Derecha;
};
vector<long long> h;
vector<Nodo> _rbol;
Nodo Combinar(Nodo a, Nodo b){
Nodo e;
e.Suma = a.Suma + b.Suma;
e.Izquierda = max(a.Izquierda, a.Suma + b.Izquierda);
e.Derecha = max(b.Derecha, b.Suma + a.Derecha);
e.Segmento = max(a.Derecha + b.Izquierda, max(a.Segmento, b.Segmento));
return e;
}
void Crear(long long Inicio, long long Final, long long Posici_n){
if(Inicio == Final){
_rbol[Posici_n].Suma = h[Inicio];
_rbol[Posici_n].Segmento = max(0LL, h[Inicio]);
_rbol[Posici_n].Izquierda = max(0LL, h[Inicio]);
_rbol[Posici_n].Derecha = max(0LL, h[Inicio]);
} else {
long long Promedio = (Inicio + Final) / 2;
Crear(Inicio, Promedio, Posici_n * 2);
Crear(Promedio + 1, Final, Posici_n * 2 + 1);
_rbol[Posici_n] = Combinar(_rbol[Posici_n * 2], _rbol[Posici_n * 2 + 1]);
}
}
Nodo Consulta(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
if(Izquierda >= Inicio and Derecha <= Final){
return _rbol[Posici_n];
}
if(Izquierda > Final or Derecha < Inicio){
Nodo E;
E.Suma = 0;
E.Segmento = 0;
E.Izquierda = 0;
E.Derecha = 0;
return E;
}
long long Promedio = (Izquierda + Derecha) / 2;
Nodo Izquierdo = Consulta(Izquierda, Promedio, Posici_n * 2, Inicio, Final);
Nodo Derecho = Consulta(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final);
Nodo E = Combinar(Izquierdo, Derecho);
return E;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
long long n = H.size() - 1;
bool _1_2 = 1;
for(long long i = 0; i <= n; i++){
h.push_back((long long)H[i]);
if(h[i] != 1 and h[i] != 2) _1_2 = 0;
}
if(_1_2){
for(long long i = 0; i <= n; i++){
if(h[i] == 2) h[i] = -22222222;
}
}
long long q = L.size();
Nodo E;
E.Suma = 0;
E.Segmento = 0;
E.Izquierda = 0;
E.Derecha = 0;
_rbol.assign(n * 4 + 22, E);
Crear(0, n, 1);
//cerr<<"Vas bien\n";
vector<long long> Respuesta(q);
for(long long i = 0; i < q; i++){
long long l = L[i];
long long r = R[i];
if(_1_2) Respuesta[i] = 2 * (r - l + 1) - Consulta(0, n, 1, l, r).Segmento;
}
return Respuesta;
}
