#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn = 1e5 + 100;
struct Node {
ll prf = 0, suf = 0, sum = 0, mx = 0;
bool operator == (Node a) {
return (a.prf == prf && a.suf == suf && a.sum == sum && a.mx == mx);
}
} null;
Node operator + (Node a, Node b) {
if (a == null) return b;
if (b == null) return a;
ll prf = a.prf;
if (a.prf == a.sum) prf += b.prf;
ll suf = b.suf;
if (b.suf == b.sum) suf += a.suf;
return {prf, suf, max({a.sum, b.sum, a.suf + b.prf}), max(a.mx, b.mx)};
}
vector<int> a;
struct SGT {
vector<Node> sgt;
SGT(int sz) {
sgt.resize(4 * sz);
}
void build(int k, int l, int r) {
if (l == r) {
sgt[k] = {a[l] == 1, a[l] == 1, a[l] == 1, a[l]};
return;
}
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
}
Node get(int k, int l, int r, int i, int j) {
if (l > j || r < i) return null;
if (i <= l && r <= j) return sgt[k];
int mid = (l + r) / 2;
return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
}
} sgt(mxn);
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size(), Q = L.size();
a = H;
vector<ll> C(Q);
sgt.build(1, 0, N - 1);
for (int i = 0; i < Q; i++) {
Node ans = sgt.get(1, 0, N - 1, L[i], R[i]);
int len = R[i] - L[i] + 1;
C[i] = ans.sum + (len - ans.sum) * ans.mx;
}
return C;
}
