#include <bits/stdc++.h>
#include "meetings.h"
#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MAXN = 1e5+ 10 ;
const ll inf = 1e17 ;
const int intInf = 1e9+10 ;
using namespace std ;
// --------------------------------
struct Seg
{
int v[MAXN*4] ;
Seg() { memset(v , 0 , sizeof v) ; }
int m(int l, int r) { return (l+r) / 2 ; }
void upd(int pos, int l, int r , int x , int val)
{
if( l == r ) { v[pos] = val ; return ; }
if( x <= m(l,r) ) upd(pos*2, l, m(l,r) , x , val) ;
else upd(pos*2+1,m(l,r)+1, r , x , val ) ;
v[pos] = max( v[pos*2] , v[pos*2+1] ) ;
}
int query(int pos, int l, int r , int beg, int en)
{
if( l > en || r < beg ) return 0 ;
if( l >= beg && r <= en ) return v[pos] ;
int al = query(pos*2 , l , m(l,r) , beg , en) ;
int ar = query(pos*2+1, m(l,r)+1, r, beg, en) ;
return max(al,ar) ;
}
void print(int pos, int l, int r)
{
printf("%d %d %d\n" , l , r , v[pos]) ;
if(l==r) return ;
print(pos*2, l , m(l,r)) ;
print(pos*2+1, m(l,r)+1, r) ;
}
} ;
int n , q , tot , val , ini ;
Seg seg ;
vector<pii> intervalR , intervalL ;
// --------------------------------
int apaga(int id , int L , int R )
{
int c = seg.query(1,0,n-1, L , R) + ( R-L+1 - c )*2 ;
if( id == tot || intervalR[id].ss > R ) return c
;
ini = intervalR[id].ss ;
if( ini < L ) return R-L+1;
val = seg.query( 1 , 0 , n-1 , ini , ini) ;
seg.upd( 1 , 0 , n-1 , ini , R-ini+1 ) ;
c = seg.query( 1 , 0 , n-1 , L , R ) ;
seg.upd( 1 , 0 , n-1 , ini , val ) ;
return c + ( R - L + 1 - c)*2 ;
}
vector<ll> minimum_costs( vector<int> h , vector<int> l , vector<int> r )
{
q = l.size() ;
n = h.size() ;
vector<ll> ans ;
int ant = MAXN ;
h.pb(2) ;
lp(i,0,n+1)
{
if( h[i] == 2 )
{
if( ant < MAXN )
{
intervalL.pb( mk(ant, i-1) ) ;
intervalR.pb( mk( i-1 , ant ) ) ;
seg.upd( 1 , 0 , n-1 , ant , i - ant ) ;
tot ++ ;
}
ant = MAXN ;
}
else ant = min( i , ant ) ;
}
lp(i,0,q)
{
int L = l[i] , R = r[i] , id ;
int tempAns = 2*(R-L+1) ;
pii p ;
//Procuro pelo primeiro tal que o r eh maior que R
//Isso significa que ele pode estar fracionado
//Seu valor nao pode ser levado em consideracao na seg, porque ela vai dar a resposta inteira
id = upper_bound( intervalR.begin() , intervalR.end() , mk(R , -1) ) - intervalR.begin() ;
tempAns = min( tempAns , apaga(id , L , R) ) ;
//Ultimo tal que o começo está entre L e R inclusive
id = lower_bound( intervalL.begin() , intervalL.end() , mk( L , -1 ) ) - intervalL.begin() - 1 ;
if( id >= 0 )
{
p = intervalL[id] ;
p.ss = min(p.ss, R) ;
if( p.ss >= L ) tempAns = min( tempAns , ( p.ss - L + 1 ) + ( R - p.ss ) * 2 ) ;
}
ans.pb(1LL*tempAns) ;
}
return ans ;
}
