#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cerr << #a << " = " << a << endl
#define lli long long int
struct x{
lli MAX;
lli Mi;
lli Md;
lli hizq;
lli hder;
};
x ST[2000000];
x act;
lli cont,n,q,res,dif;
vector<lli> total;
void creah(int pos) {
ST[pos].hizq = cont++;
ST[pos].hder = cont++;
}
void rango(lli nodo, lli ini, lli fin, lli l, lli r){
lli mitad,tra;
if (ini >= l && r >= fin) {
if (act.MAX == -1) act = ST[nodo];
else {
act.MAX = max(act.MAX, ST[nodo].MAX);
tra = act.Md + ST[nodo].Mi;
act.MAX = max(act.MAX, tra);
if (fin-ini+1 == ST[nodo].Md) act.Md += ST[nodo].Md;
act.Md = ST[nodo].Md;
}
}
else if (ini > r || fin < l) return;
else {
mitad = (ini+fin) /2;
if (ST[nodo].hizq == 0) creah(nodo);
rango(ST[nodo].hizq,ini,mitad,l,r);
rango(ST[nodo].hder,mitad+1,fin,l,r);
}
}
void actualiza(lli nodo, lli ini, lli fin, lli des) {
lli mitad,uni;
if (ini == fin && ini == des) {
ST[nodo].MAX = 1;
ST[nodo].Mi = 1;
ST[nodo].Md = 1;
}
else if (ini <= des && fin >= des) {
mitad = (ini + fin) /2;
if (ST[nodo].hizq == 0) creah(nodo);
actualiza(ST[nodo].hizq,ini,mitad,des);
actualiza(ST[nodo].hder,mitad+1,fin,des);
ST[nodo].MAX = max(ST[ ST[nodo].hizq ].MAX, ST[ ST[nodo].hder ].MAX);
uni = ST[ ST[nodo].hizq ].Md + ST[ ST[nodo].hder ].Mi;
ST[nodo].MAX = max(uni, ST[nodo].MAX);
if (mitad-ini+1 == ST[ ST[nodo].hizq ].Mi) ST[nodo].Mi = ST[ ST[nodo].hizq ].Mi + ST[ ST[nodo].hder ].Mi;
else ST[nodo].Mi = ST[ ST[nodo].hizq ].Mi;
if (fin-mitad == ST[ ST[nodo].hder ].Md) ST[nodo].Md = ST[ ST[nodo].hder ].Md + ST[ ST[nodo].hizq ].Md;
else ST[nodo].Md = ST[ ST[nodo].hder ].Md;
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
cont = 2;
n = H.size();
n--;
q = L.size();
rep (i,0,n) if (H[i] == 1) actualiza(1,0,n,i);
rep(i,0,q-1) {
act = {-1,-1,-1,-1,-1};
rango(1,0,n,L[i],R[i]);
res = act.MAX;
dif = R[i] - L[i] + 1;
res += 2*(dif - res);
total.push_back(res);
}
return total;
}
