#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second

const int maxn = 1e6 + 10;

int n, q;
ll pref[maxn], a[maxn], t[maxn * 4];

void upd(int v, int tl, int tr, int p, int val) {
	if (tl == tr) {
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (p <= tm) {
		upd(v * 2, tl, tm, p, val);
	} else {
		upd(v * 2 + 1, tm + 1, tr, p, val);
	}
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) {
		return 0;
	}
	if (tl >= l && tr <= r) {
		return t[v];
	}
	int tm = (tl + tr) / 2;
	return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	n = H.size();
	q = L.size();
	vector <ll> c(q);
	pref[0] = H[0];
	a[0] = (H[0] == 1);
	upd(1, 0, n - 1, 0, a[0]);
	for (int i = 1; i < n; i++) {
		pref[i] = pref[i - 1] + H[i];
	}
	for (int i = 1; i < n; i++) {
		if (H[i] == 1) {
			a[i] = a[i - 1] + 1;
		} else {
			a[i] = 0;
		}
		upd(1, 0, n - 1, i, a[i]);
	}
	for (int i = 0; i < q; i++) {
		int mx = 0;
		if (H[L[i]] == 1) {
			int l = L[i], r = R[i] + 1;
			int x = 0;
			if (l > 0) {
				x = pref[l - 1];
			}
			while(r - l > 1) {
				int md = (l + r) / 2;
				if (pref[md] - x == md - l + 1) {
					l = md;
				} else {
					r = md;
				}
			}
			mx = max(mx, l - L[i] + 1);
			if (r <= R[i]) {
				mx = max(mx, get(1, 0, n - 1, r, R[i]));
			}
		} else {
			mx = get(1, 0, n - 1, L[i], R[i]);
		}
		c[i] =  2 * (R[i] - L[i] + 1) - mx;
	}
	return c;
}