#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct segment_tree {
int n;
vector<int> tree;
segment_tree(int _n) : n(_n), tree(4*n) {}
void update(int u, int tl, int tr, int p, int v) {
if(tl == tr) {
tree[u] = max(tree[u], v);
} else {
int tm = (tl + tr) / 2;
if(p <= tm) update(2*u, tl, tm, p, v);
else update(2*u+1, tm+1, tr, p, v);
tree[u] = max( tree[2*u], tree[2*u+1] );
}
}
int query(int u, int tl, int tr, int l, int r) {
if(tl > r || l > tr) return 0;
if(l <= tl && tr <= r) return tree[u];
int tm = (tl + tr) / 2;
return max( query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r) );
}
void update(int p, int v) { update(1, 0, n-1, p, v); }
int query(int l, int r) { return query(1, 0, n-1, l, r); }
};
vector<ll> minimum_costs(vector<int> a, vector<int> L, vector<int> R) {
int q = L.size(), n = a.size();
vector<ll> ans(q, 1e18);
vector<int> pref(n, -1), suf(n, n+1);
int lst = -1;
set<pair<int, int> > B;
for(int i=0; i<n; i++) {
if(a[i] == 1) {
B.insert({ i, lst+1 });
pref[lst+1] = max(pref[lst+1], i);
suf[i] = min(suf[i], lst+1);
} else if(a[i] == 2) {
lst = i;
}
}
for(int i=1; i<n; i++) pref[i] = max(pref[i-1], pref[i]);
for(int i=n-2; i>=0; i--) suf[i] = min(suf[i+1], suf[i]);
for(int i=0; i<q; i++) {
if(L[i] > 0 && pref[L[i]-1] >= L[i]) {
int len = min(R[i], pref[L[i]-1]) - L[i] + 1;
ans[i] = min(ans[i], 2ll * (R[i] - L[i] + 1) - len);
}
if(R[i] < n - 1 && suf[R[i]+1] <= R[i]) {
int len = R[i] - max(L[i], suf[R[i]+1]) + 1;
ans[i] = min(ans[i], 2ll * (R[i] - L[i] + 1) - len);
}
}
segment_tree sgt(n);
vector<pair<int, int> > qus[n];
for(int i=0; i<q; i++) qus[R[i]].push_back({ L[i], i });
for(int i=0; i<n; i++) {
while(!B.empty() && B.begin()->first == i) {
sgt.update(B.begin()->second, i - B.begin()->second + 1);
B.erase( B.begin() );
}
for(auto [l, id] : qus[i])
ans[id] = min(ans[id], 2ll * (i - l + 1) - sgt.query(l, i));
}
return ans;
}
