#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
const int lg = 20;
int n, q;
ll h[maxn], mx[lg][maxn];
vector<int> idx;
ll getmx(int l, int r){
r++;
int x = 31 - __builtin_clz(r-l);
//debug(l, r, x);
return max(mx[l][x], mx[r-(1<<x)][x]);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
idx.push_back(-1);
for (int i = 0; i < n; i++){
h[i] = H[i];
if (h[i] == 2) idx.push_back(i);
}
idx.push_back(n);
for (int i = 0; i < n; i++){
int r = lower_bound(all(idx), i) - idx.begin();
int l = upper_bound(all(idx), i) - idx.begin() - 1;
mx[0][i] = max(0, idx[r] - idx[l] - 1);
//debug(i, mx[0][i]);
}
for (int i = 1; i < lg; i++){
for (int j = 0; j + (1 << i) <= n; j++){
mx[i][j] = max(mx[i-1][j], mx[i-1][j+(1<<(i-1))]);
//debug(i, j, mx[i][j]);
}
}
vector<ll> res;
for (int i = 0; i < q; i++){
int l = lower_bound(all(idx), L[i]) - idx.begin();
int r = upper_bound(all(idx), R[i]) - idx.begin() - 1;
if (r < l){
res.push_back(R[i]-L[i]+1);
continue;
}
assert(l >= L[i] && r <= R[i]);
//debug(L[i], R[i], idx[l], idx[r]);
int bst = max({(ll)idx[l] - L[i], (ll)R[i] - idx[r], getmx(idx[l], idx[r])});
res.push_back((R[i]-L[i]+1)*2-bst);
}
return res;
}
