#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#include "meetings.h"
int max(int a, int b, int c)
{
return max(max(a, b), c);
}
struct node
{
int in, l, r, b, e;
};
int max(node n)
{
return max(n.in, n.l, n.r);
}
node operator+(node const &l, const node &r)
{
node tmp;
tmp.in = max(l.in, r.in, l.r + r.l);
tmp.l = (l.l == l.e - l.b ? l.l + r.l : l.l);
tmp.r = (r.r == r.e - r.b ? r.r + l.r : r.r);
tmp.b = l.b;
tmp.e = r.e;
return tmp;
}
struct segmenttree
{
vector<node> tree;
void initialise(vector<int> const &H)
{
tree.resize(1 << (__lg(H.size() - 1) + 2));
init(1, 0, H.size(), H);
}
node init(int index, int b, int e, vector<int> const &H)
{
if (e - b == 1)
return tree[index] = {(H[b] == 1 ? 1 : 0), (H[b] == 1 ? 1 : 0), (H[b] == 1 ? 1 : 0), b, e};
tree[index] = init(index * 2, b, (b + e) / 2, H) + init(index * 2 + 1, (b + e) / 2, e, H);
return tree[index];
}
node query(int index, int b, int e, int l, int r)
{
if (l <= b && e <= r + 1)
return tree[index];
if (e <= l || r < b)
return {0, 0, 0, 0, INT32_MAX};
node tmp = query(index * 2, b, (e + b) / 2, l, r) + query(index * 2 + 1, (e + b) / 2, e, l, r);
return tmp;
}
} tree;
long long findmin(int l, int r, std::vector<int> const &H)
{
long long sum = (r - l + 1) * 2 - max(tree.query(1, 0, H.size(), l, r));
return sum;
}
std::vector<long long> minimum_costs(std::vector<int> H,
std::vector<int> L,
std::vector<int> R)
{
tree.initialise(H);
int Q = L.size();
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j)
{
C[j] = findmin(L[j], R[j], H);
}
return C;
}
