#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
const ll inf = 1e9 + 10;
const int maxn = 1e5 + 10;
vector<int> seg( 4*maxn );
void build( int pos, int ini, int fim, vector<int>& idL, vector<int>& idR ){
if( ini == fim ){ seg[pos] = idR[ini] - idL[ini] - 1; return; }
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
build( l, ini, mid, idL, idR );
build( r, mid + 1, fim, idL, idR );
seg[pos] = max( seg[l], seg[r] );
}
int query( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return 0;
if( ki <= ini && fim <= kf ) return seg[pos];
int mid = ( ini + fim )/2;
return max( query( 2*pos, ini, mid, ki, kf ), query( 2*pos + 1, mid + 1, fim, ki, kf ) );
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = H.size(), q = L.size();
vector<ll> resp(q);
if( q <= 50000 ){
vector<ll> respL(n);
for( int i = 0; i < q; i++ ){
int l = L[i], r = R[i];
resp[i] = inf*inf;
stack<pair<int,ll>> pilha;
pilha.push({ l - 1, inf });
ll sum = 0;
for( int j = l; j <= r; j++ ){
while( pilha.top().second <= H[j] ){
auto [id, v] = pilha.top(); pilha.pop();
sum -= 1LL*v*abs(id - pilha.top().first);
}
sum += 1LL*H[j]*abs(j - pilha.top().first);
pilha.push({ j, H[j] });
respL[j] = sum;
}
while( !pilha.empty() ) pilha.pop();
pilha.push({ r + 1, inf });
sum = 0;
for( int j = r; j >= l; j-- ){
while( pilha.top().second <= H[j] ){
auto [id, v] = pilha.top(); pilha.pop();
sum -= 1LL*v*abs(id - pilha.top().first);
}
sum += 1LL*H[j]*abs(j - pilha.top().first);
pilha.push({ j, H[j] });
resp[i] = min( resp[i], sum + respL[j] - H[j] );
}
}
return resp;
}
vector<int> idL(n), idR(n);
idL[0] = (( H[0] == 2 ) ? 0 : -1 );
for( int i = 1; i < n; i++ ) idL[i] = (( H[i] == 2 ) ? i : idL[i - 1] );
idR[n - 1] = (( H[n - 1] == 2 ) ? n - 1 : n );
for( int i = n - 2; i >= 0; i-- ) idR[i] = (( H[i] == 2 ) ? i : idR[i + 1] );
build( 1, 0, n - 1, idL, idR );
for( int i = 0; i < q; i++ ){
int l = L[i], r = R[i];
resp[i] = 2*(r - l + 1) - max({ idR[l] - l, r - idL[r], query( 1, 0, n - 1, idR[l], idL[r] ) });
}
return resp;
}
