#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "meetings.h"
const long long inf = 1e17;
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
*/
vector<vector<int> > mx;
int M, K;
int query(int l, int r){
int ind = 0;
while((1 << (ind + 1)) <= (r - l + 1)){
ind++;
}
return max(mx[l][ind], mx[r - (1 << ind) + 1][ind]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int n = H.size();
vector<array<int, 3> > segments;
int cnt = 0;
for(int i = 0; i < n; i++){
if(H[i] == 2){
if(cnt > 0){
segments.pb({i - cnt, i - 1, cnt});
}
cnt = 0;
}
else cnt++;
}
if(cnt > 0){
segments.pb({n-cnt, n-1, cnt});
}
M = segments.size();
K = 18;
if(M > 0){
mx.resize(M);
for(int i = 0; i < M; i++){
mx[i].resize(K);
mx[i][0] = segments[i][2];
}
for(int i = 1; i < K; i++){
for(int j = 0; j < M; j++){
mx[j][i] = max(mx[j][i-1], mx[min(M-1, j + (1 << (i - 1)))][i-1]);
}
}
}
int Q = L.size();
vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
long long ans = 2 * (R[j] - L[j] + 1);
if(M > 0){
int l = 0, r = M-1;
while(l < r){
int m = (l + r)/2;
if(segments[m][1] >= L[j]) r = m;
else l = m + 1;
}
int sol = l;
l = 0, r = M-1;
while(l < r){
int m = (l + r + 1)/2;
if(segments[m][0] <= R[j]) l = m;
else r = m - 1;
}
int sag = l;
int cik = 0;
if(segments[sol][0] < L[j]){
cik = max(cik, segments[sol][1] - L[j] + 1);
sol++;
}
if(segments[sag][1] > R[j]){
cik = max(cik, R[j] - segments[sag][0] + 1);
sag--;
}
if(sol <= sag){
cik = max(cik, query(sol, sag));
}
ans -= cik;
}
C[j] = ans;
}
return C;
}
/*
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;
}*/
