#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
using namespace std;
vector<vector<ll> > tree(400005, vector<ll>(3));
vector<int> h;
void build(int indx, int st, int end) {
if (st == end) {
if (h[st] == 1)
tree[indx] = {1, 1, 1};
else
tree[indx] = {0, 0, 0};
return;
}
int mid = (st + end) / 2;
build(indx*2, st, mid);
build(indx*2+1, mid+1, end);
if (tree[indx*2][0] == mid-st+1)
tree[indx][0] = tree[indx*2][0] + tree[indx*2+1][0];
else
tree[indx][0] = tree[indx*2][0];
if (tree[indx*2+1][2] == end-mid)
tree[indx][2] = tree[indx*2][2] + tree[indx*2+1][2];
else
tree[indx][2] = tree[indx*2+1][2];
tree[indx][1] = max(max(tree[indx*2][1], tree[indx*2+1][1]), max(tree[indx][0], tree[indx][2]));
tree[indx][1] = max(tree[indx][1], tree[indx*2][2]+tree[indx*2+1][0]);
}
vector<ll> query(int indx, int st, int end, int l, int r) {
if (st > r || end < l)
return {0, 0, 0};
if (l <= st && end <= r)
return tree[indx];
int mid = (st + end) / 2;
vector<ll> left = query(indx*2, st, mid, l, r);
vector<ll> right = query(indx*2+1, mid+1, end, l, r);
vector<ll> ans(3);
if (left[0] == mid-st+1)
ans[0] = left[0] + right[0];
else
ans[0] = left[0];
if (right[2] == end-mid)
ans[2] = left[2] + right[2];
else
ans[2] = right[2];
ans[1] = max(max(left[1], right[1]), max(ans[0], ans[2]));
ans[1] = max(ans[1], left[2]+right[0]);
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = H.size(), mx, Q = L.size();
h = H;
build (1, 0, n-1);
vector<long long> ans(Q);
for (int q = 0; q < Q; q++) {
ans[q] = (R[q]-L[q]+1)*2 - query(1, 0, n-1, L[q], R[q])[1];
}
return ans;
}
/*
3 3
2 1 2
0 0
0 1
0 2
*/
