#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree {
vector<int> T;
segtree(int sz) { T.resize(4*sz); }
void init(vector<int>& A, int idx, int s, int e) {
if(s == e) {
T[idx] = A[s-1];
return;
}
int m = s+e >> 1;
init(A, idx*2, s, m);
init(A, idx*2+1, m+1, e);
T[idx] = max(T[idx*2], T[idx*2+1]);
}
int get(int idx, int s, int e, int l, int r) {
if(r < s || e < l) return -1e9;
if(l <= s && e <= r) return T[idx];
int m = s+e >> 1;
return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
}
};
int MH[5009][5009], Lg[100009], Rg[100009];
long long PS[5009][5009];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size(), N = H.size();
vector<long long> C(Q);
if(Q <= 5000 && N <= 5000) {
for(int i=0; i<N; i++) {
for(int j=i, mx=H[i]; j>=0; j--) mx = max(mx, H[j]), MH[i][j] = mx;
for(int j=i, mx=H[i]; j<N; j++) mx = max(mx, H[j]), MH[i][j] = mx;
PS[i][0] = MH[i][0];
for(int j=1; j<N; j++) PS[i][j] = PS[i][j-1] + MH[i][j];
}
for(int i=0; i<Q; i++) {
long long ans = 1LL * 1e18;
for(int j=L[i]; j<=R[i]; j++) {
long long x = PS[j][R[i]] - (L[i] ? PS[j][L[i]-1] : 0);
ans = min(ans, x);
}
C[i] = ans;
}
return C;
}
vector<int> A(N);
for(int i=0, s=0; i<N; i++) {
if(H[i] == 1) ++s;
else s = 0;
A[i] = s;
}
int l = -1;
for(int i=0; i<N; i++) {
if(H[i] == 2) l = i;
Lg[i] = l;
}
int r = N;
for(int i=N-1; i>=0; i--) {
if(H[i] == 2) r = i;
Rg[i] = r;
}
segtree seg(N+1);
seg.init(A, 1, 1, N);
for(int i=0; i<Q; i++) {
int mx = 0, ans = 2 * (R[i] - L[i] + 1);
if(H[L[i]] == 1) mx = max(mx, Rg[L[i]] - L[i]), L[i] = Rg[L[i]];
if(H[R[i]] == 1) mx = max(mx, R[i] - Lg[R[i]]), R[i] = Lg[R[i]];
mx = max(mx, seg.get(1, 1, N, L[i]+1, R[i]+1));
C[i] = ans - mx;
}
return C;
}
