#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
vector<long long> coutsMin;
int nMonts = H.size(), nReqs = R.size();
vector<int> hauteurs = H;
vector<int> droite(nMonts), gauche(nMonts), taille(nMonts);
int pt = -1;
for (int iMont = 0; iMont < nMonts; ++iMont){
if (hauteurs[iMont] != 0)
pt = iMont;
gauche[iMont] = pt;
}
pt = nMonts;
for (int iMont = nMonts - 1; iMont >= 0; --iMont){
if (hauteurs[iMont] != 0)
pt = iMont;
droite[iMont] = pt;
}
for (int iMont = 0; iMont < nMonts; ++iMont)
taille[iMont] = droite[iMont] - gauche[iMont] - 1;
int tTree = (1 << ((int)ceil(log2(nMonts))));
vector<int> tree(tTree * 2);
for (int &noeud : tree)
noeud = 0;
for (int i = 0; i < nMonts; ++i)
tree[i + tTree] = taille[i];
for (int i = tTree - 1; i > 0; --i)
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
for (int iReq = 0; iReq < nReqs; ++iReq){
int gaucheReq = L[iReq], droiteReq = R[iReq], tailleInter = droiteReq - gaucheReq + 1;
int minimum = 750000;
minimum = min(minimum, tailleInter - (droite[gaucheReq] - gaucheReq));
gaucheReq = droite[gaucheReq ] + 1;
minimum = min(minimum, tailleInter - (droiteReq - gauche[droiteReq]));
droiteReq = gauche[droiteReq] - 1;
droiteReq += tTree;
gaucheReq += tTree;
int maxCouvert = 0;
while (droiteReq > gaucheReq){
if (gaucheReq%2 == 1){
maxCouvert = max(maxCouvert, tree[gaucheReq]);
gaucheReq++;
}
else if (droiteReq%2 == 0){
maxCouvert = max(maxCouvert, tree[droiteReq]);
droiteReq--;
}
else {
droiteReq /= 2;
gaucheReq /= 2;
}
}
//cout << maxCouvert;
minimum = min(minimum, tailleInter - maxCouvert);
coutsMin.push_back(minimum);
}
return coutsMin;
}
