#include <bits/stdc++.h>
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define sz size()
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define pb push_back
const int MAXN=5e5+10 ;
const int MAXS = 2e5+10 ;
using namespace std ;
struct persistentSeg
{
vector<int> e , d , soma ;
int m(int l , int r) { return (l+r)/2 ; }
int create()
{
e.pb(-1) ;
d.pb(-1) ;
soma.pb(0) ;
return e.sz-1 ;
}
int createAndCopy(int idx)
{
e.pb(e[idx]) ;
d.pb(d[idx]) ;
soma.pb(soma[idx]) ;
return e.sz-1 ;
}
int updPoint(int pos, int l ,int r , int idx, int val)
{
int novo = pos == -1 ? create() : createAndCopy(pos) ;
if(l==r)
{
soma[novo] += val ;
return novo ;
}
int aux ;
if( idx <= m(l,r) )
{
aux = updPoint(e[novo],l,m(l,r),idx,val) ;
e[novo]=aux ;
}
else
{
aux = updPoint( d[novo] , m(l,r)+1, r , idx , val ) ;
d[novo] = aux ;
}
int al = e[novo] == -1 ? 0 : soma[e[novo]] ;
int ar=d[novo] == -1 ? 0 : soma[d[novo]] ;
soma[novo] = al + ar ;
return novo ;
}
void print(int pos, int l , int r)
{
if(pos==-1) return ;
printf("%d %d -> %d\n" , l ,r , soma[pos]) ;
if(l==r) return;
print(e[pos],l,m(l,r)) ;
print(d[pos],m(l,r)+1,r) ;
}
int qry(int pos , int l , int r , int beg, int en)
{
if( l > en || r < beg || pos == -1) return 0 ;
if( l >= beg && r <=en ) return soma[pos] ;
int al = qry( e[pos] , l , m(l,r) , beg, en ) ;
int ar = qry(d[pos] , m(l,r)+1, r, beg, en) ;
return al+ar ;
}
} ;
// --------------------------------------
int rt[MAXN] ;
persistentSeg seg;
int littleQry(int x1, int x2 , int y1, int y2)
{
int rt1 = x1 == 0 ? rt[0] : rt[x1-1] , rt2 = rt[x2] ;
return seg.qry( rt2 , 0 , MAXN , y1 - 1 , y2 ) - seg.qry( rt1 , 0 , MAXN , y1-1, y2 ) ;
}
void init(int n , int a[] , int b[])
{
vector<pii> v , temp ;
rt[0] = seg.create() ;
temp.pb( {rt[0] , 0} ) ;
lp(i,0,n) v.pb({a[i],b[i]}) ;
sort(v.begin() , v.end()) ;
lp(i,0,n)
temp.pb( mk( seg.updPoint( temp[ temp.sz-1 ].ff , 0 , MAXN , v[i].ss , 1 ) , v[i].ff ) ) ;
lp( i , 0 , temp.sz-1 )
if( temp[i].ss != temp[i+1].ss )
rt[ temp[i].ss ] = temp[i].ff ;
pii last = temp[ temp.sz-1 ] ;
rt[ last.ss ] = last.ff ;
for(int i = 1 ; i <=MAXN ; i++ )
if( rt[i] == 0 ) rt[i] = rt[i-1] ;
}
void print(stack<tuple<int,int,int> > s)
{
if(s.empty()) printf("It's empty already!\n") ;
while(!s.empty())
{
tuple<int,int,int> Top = s.top() ;
s.pop() ;
printf("%d %d %d\n", get<0>(Top) , get<1>(Top) , get<2>(Top) ) ;
}
}
bool can(int m , int k[])
{
stack< tuple<int,int,int> > frontier ;
bool ok = true ;
sort( k , k + m ) ;
frontier.push( make_tuple( 0 , MAXN , 0 ) ) ;
//"Frontier"'s meaning: last x I took and how much I took
//The goal is that "alreadyRemoved" will never be 0
//Each x at the stack will be unique
for(int i = m-1 ; i >= 0 ; i-- )
{
tuple<int,int,int> Top ;
int x , y , alreadyRemoved , carry = 0 ;
//print(frontier) ;
while( !frontier.empty() )
{
Top = frontier.top() ;
x = get<0>(Top) ;
y = get<1>(Top) ;
alreadyRemoved = get<2>(Top) ;
if( x <= k[i] ) carry += alreadyRemoved ;
if( x > k[i] || littleQry( x , k[i] , k[i] , y ) < k[i] + alreadyRemoved ) frontier.pop() ;
else break ;
}
//print(frontier);
if( frontier.empty() ) { ok = false; break ; }
int l = x+1 , r = k[i] , mid , best = -1 ;
while( l <= r )
{
mid = (l+r)/2 ;
if( littleQry(mid , k[i] , k[i], y ) >= k[i] + carry )
{
best = mid ;
l = mid + 1 ;
}
else r = mid -1 ;
}
if( best == -1 ) { ok = false ; continue ; }
frontier.push( make_tuple( best, k[i] , k[i] - littleQry( best+1 , k[i] , k[i] , y ) ) ) ;
}
return ok ;
}
