#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
const int K = 22;
vector<int> lw;
int get_mx(int l, int r, vector<vector<int>>& mx){
int dist = r - l + 1;
int k = lw[dist];
return max(mx[k][r], mx[k][l + (1 << k) - 1]);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
int n = (int)H.size();
int q = (int)L.size();
if(n <= 5000 && q <= 5000){
vector<vector<ll>> prefix(n, vector<ll>(n, 0));
for(int i = 0; i < n; i++){
vector<int> val(n, 0);
int mx = 0;
for(int j = i; j >= 0; j--){
mx = max(mx, H[j]);
val[j] = mx;
}
mx = 0;
for(int j = i; j < n; j++){
mx = max(mx, H[j]);
val[j] = mx;
}
for(int j = 0; j < n; j++){
if(j == 0) prefix[i][j] = val[j];
else prefix[i][j] = prefix[i][j-1] + val[j];
}
}
vector<ll> ans(q, 1e18);
for(int k = 0; k < q; k++){
int l = L[k];
int r = R[k];
for(int i = l; i <= r; i++){
ll sum = prefix[i][r];
if(l > 0) sum -= prefix[i][l-1];
ans[k] = min(ans[k], sum);
}
}
return ans;
}else{
//H[i] <= 2.
lw.resize(n+1);
int pw = 0;
int curr = 2;
for(int i = 1; i <= n; i++){
if(i == curr){pw++; curr *= 2;}
lw[i] = pw;
}
set<int> two;
for(int i = 0; i < n; i++){
if(H[i] == 2) two.insert(i);
}
vector<int> val(n);
for(int i = 0; i < n; i++){
if(H[i] == 2){
val[i] = 0;
continue;
}
auto it = two.upper_bound(i);
int l, r;
if(it == two.end()){
r = n;
}else r = *it;
if(it == two.begin()){
l = -1;
}else{
it--;
l = *it;
}
val[i] = r - l - 1;
}
vector<vector<int>> mx(K, vector<int>(n));
for(int k = 0; k < K; k++){
for(int i = 0; i < n; i++){
if(k == 0) mx[k][i] = val[i];
else{
if(i - (1 << (k-1)) < 0) mx[k][i] = mx[k-1][i];
else mx[k][i] = max(mx[k-1][i], mx[k-1][i - (1 << (k-1))]);
}
}
}
vector<ll> ans(q);
for(int k = 0; k < q; k++){
int l = L[k];
int r = R[k];
int _mx = 0;
int first = -1;
int second = r + 1;
auto it = two.lower_bound(l);
if(it != two.end() && *it <= r) first = *it;
it = two.upper_bound(r);
if(it != two.begin()){
it--;
if(*it >= l) second = *it;
}
if(first == -1) ans[k] = (r - l + 1);
else{
_mx = max(get_mx(first, second, mx), max(first - l, r - second));
ans[k] = (r - l + 1) * 2 - _mx;
}
}
return ans;
}
}
//~ namespace {
//~ int read_int() {
//~ int x;
//~ if (scanf("%d", &x) != 1) {
//~ fprintf(stderr, "Error while reading input\n");
//~ exit(1);
//~ }
//~ return x;
//~ }
//~ } // namespace
//~ int main() {
//~ int N = read_int();
//~ int Q = read_int();
//~ std::vector<int> H(N);
//~ for (int i = 0; i < N; ++i) {
//~ H[i] = read_int();
//~ }
//~ std::vector<int> L(Q), R(Q);
//~ for (int j = 0; j < Q; ++j) {
//~ L[j] = read_int();
//~ R[j] = read_int();
//~ }
//~ std::vector<long long> C = minimum_costs(H, L, R);
//~ for (size_t j = 0; j < C.size(); ++j) {
//~ printf("%lld\n", C[j]);
//~ }
//~ return 0;
//}
