#define ll long long
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
ll left(ll i)
{
return 2*i;
}
ll right(ll i)
{
return 2*i+1;
}
struct node
{
ll bleft;
ll bright;
ll bmax;
ll len;
};
node combine(node l, node r)
{
node output = {0, 0, 0, 0};
if(l.bleft == l.len)
{
output.bleft = l.bleft + r.bleft;
}
else
{
output.bleft = l.bleft;
}
if(r.bright == r.len)
{
output.bright = r.bright+l.bright;
}
else
{
output.bright = r.bright;
}
output.bmax = max(max(r.bmax, l.bmax), r.bleft + l.bright);
output.len = l.len+r.len;
return output;
}
node query(ll i, vector<node>& s, ll a, ll b, ll l, ll r)
{
if(l <= a && b <= r)
{
return s[i];
}
if(r < a || b < l)
{
return {0, 0, 0, 0};
}
ll mid = (a+b)/2;
return combine(query(left(i), s, a, mid, l, r), query(right(i), s, mid+1, b, l, r));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
ll n = H.size();
ll segnodes = 1;
while(2*n > segnodes)
{
segnodes *= 2;
}
vector<node> s(segnodes, {0, 0, 0, 1});
for(ll i = 0; i < n; i++)
{
if(H[i] == 1)
{
s[i+segnodes/2] = {1, 1, 1, 1};
}
}
for(ll i = segnodes/2-1; i > 0; i--)
{
s[i] = combine(s[left(i)], s[right(i)]);
}
vector<ll> output(0);
for(ll i = 0; i < (ll) L.size(); i++)
{
ll mountains = R[i]+1-L[i];
output.push_back(2*mountains - query(1, s, 1, segnodes/2, L[i]+1, R[i]+1).bmax);
}
return output;
}
