#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "meetings.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;
const int MAXN = 5010;
const LL INF = 1e10;
int N, Q;
LL h[MAXN];
LL cnt[MAXN][20];
LL cl[MAXN], cr[MAXN];
LL query(int l, int r) {
LL tot = 0;
vector<pii> v; // {index, value}
v.eb(l - 1, INF);
For(i, l, r) {
while(v.back().S < h[i]) {
auto p = v.back(); v.pop_back();
tot -= p.S * (p.F - v.back().F);
}
tot += h[i] * (i - v.back().F);
cl[i] = tot;
v.eb(i, h[i]);
}
tot = 0;
v.clear();
v.eb(r + 1, INF);
Forr(i, r, l) {
while(v.back().S < h[i]) {
auto p = v.back(); v.pop_back();
tot -= p.S * (v.back().F - p.F);
}
tot += h[i] * (v.back().F - i);
cr[i] = tot;
v.eb(i, h[i]);
}
LL ans = cl[l] + cr[l] - h[l];
For(i, l + 1, r) ans = min(ans, cl[i] + cr[i] - h[i]);
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
N = sz(H);
Q = sz(L);
For(i, 0, N - 1) h[i] = H[i];
// if(N <= 5000) {
// vector<LL> C(Q);
// For(i, 0, Q - 1) {
// C[i] = query(L[i], R[i]);
// }
// return C;
// }
vector<LL> le, ri;
le.eb(-1); ri.eb(-1);
int now = 0;
For(i, 0, N - 1) {
if(h[i] == 2) now = 0;
else now++;
cnt[i][0] = now;
// cout << i << " " << h[i] << " " << now << "\n";
if(h[i] == 1) {
if(i == 0 || h[i - 1] != 1) le.eb(i);
if(i == N - 1 || h[i + 1] != 1) ri.eb(i);
}
}
le.eb(N); ri.eb(N);
For(j, 1, 19) For(i, 0, N - 1) {
cnt[i][j] = cnt[i][j - 1];
if(i + (1 << (j - 1)) < N) cnt[i][j] = max(cnt[i][j], cnt[i + (1 << (j - 1))][j - 1]);
}
auto get_max = [&](int a, int b) {
int k = __lg(b - a + 1);
return max(cnt[a][k], cnt[b - (1 << k) + 1][k]);
};
// for(auto &i:le) cout << i << " "; cout << endl;
// for(auto &i:ri) cout << i << " "; cout << endl;
vector<LL> C;
For(i, 0, Q - 1) {
LL a = L[i];
LL b = R[i];
LL ll = *lower_bound(all(le), a);
LL lr = lower_bound(all(ri), a) - ri.begin();
LL rl = prev(upper_bound(all(le), b)) - le.begin();
LL rr = *prev(upper_bound(all(ri), b));
// cout << ll << " " << lr << " " << rl << " " << rr << "\n" << flush;
if(le[lr] > b || ri[rl] < a) {
C.eb(2ll * (b - a + 1));
continue;
}
LL mx = 0;
if(ll <= rr) {
mx = max(mx, get_max(ll, rr));
}
if(ri[lr] >= a && le[lr] <= a) {
mx = max(mx, ri[lr] - a + 1);
}
if(le[rl] <= b && ri[rl] >= b) {
mx = max(mx, b - le[rl] + 1);
}
mx = min(mx, b - a + 1);
C.eb(2ll * (b - a + 1) - mx);
}
return C;
}
