#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define le node*2
#define ri node*2+1
#define pb push_back
typedef long long ll ;
typedef vector < int > vi ;
typedef vector < ll > vll ;
const ll inf = 1e18 ;
#include "meetings.h"
ll n , q ;
ll h [100009] ;
struct NODE {
ll pre , suf , ans , sz ;
} tree [400009] ;
NODE merge ( NODE x , NODE y ) {
NODE ret ;
ret .sz = x .sz + y .sz ;
ret .ans = max ( x . ans , y .ans ) ;
ret .pre = ( x .pre == x .sz ? x .pre + y .pre : x .pre ) ;
ret .suf = ( y .suf == y .sz ? y .suf + x .suf : y .suf ) ;
ret .ans = max ( ret .ans , x .suf + y .pre ) ;
ret .ans = max ( ret .ans , max ( ret .pre , ret .suf ) ) ;
return ret ;
}
void build ( int node , int l , int r ) {
if ( l == r ) {
int x = ( h [l] == 1 ) ;
tree [node] = { x , x , x , 1 } ;
return ;
}
build ( le , l , mid ) ;
build ( ri , mid + 1 , r ) ;
tree [node] = merge ( tree [le] , tree [ri] ) ;
}
NODE query ( int node , int l , int r , int s , int e ) {
if ( s <= l && e >= r ) return tree [node] ;
if ( s <= mid && e >= mid + 1 ) return merge ( query ( le , l , mid , s , e ) , query ( ri , mid + 1 , r , s , e ) ) ;
else if ( s <= mid ) return query ( le , l , mid , s , e ) ;
else return query ( ri , mid + 1 , r , s , e ) ;
}
vll minimum_costs ( vi H , vi L , vi R) {
n = H .size () , q = L .size () ;
for ( ll i = 0 ; i < n ; i ++ ) {
h [i] = H [i] ;
}
build ( 1 , 0 , n -1 ) ;
vll ans ;
for ( int i = 0 ; i < q ; i ++ ) {
ll l = L [i] , r = R [i] ;
ll sz = query ( 1 , 0 , n -1 , l , r ) .ans ;
ll more = ( r - l + 1 ) - sz ;
ans .pb ( sz + more * 2ll ) ;
}
return ans ;
}
