#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] , rootByX[MAXN] ;
persistentSeg seg;
vector<pii> xPossible ;
int littleQry(int x1, int x2 , int y1, int y2)
{
int rt1 = 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[])
{
rt[0] = seg.create() ;
xPossible.pb({0,0}) ;
vector<pii> v ;
lp(i,0,n) v.pb({a[i],b[i]}) ;
sort(v.begin() , v.end()) ;
lp(i, 1, n+1 )
{
rt[i] = seg.updPoint( rt[i-1] , 0 , MAXN , v[i-1].ss , 1 );
if( xPossible[ xPossible.sz-1 ].ff < v[i-1].ff ) xPossible.pb( {v[i-1].ff , rt[i]} ) ;
else xPossible[ xPossible.sz-1 ].ss = rt[i] ;
}
lp(i,0, xPossible.sz )
{
pii p = xPossible[i] ;
rootByX[ p.ff ] = i ;
}
for(int i = 1 ; i <= MAXN ; i++ )
if( rt[i] == 0 ) rt[i] = rt[i-1] ;
}
void print(stack<tuple<int,int,int> > s)
{
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(1,MAXN , 0) ) ;
for(int i = m-1 ; i >= 0 ; i-- )
{
int am = k[i] , tot = 0 , x , y , alreadyRemoved ;
tuple<int,int,int> Top ;
//print(frontier) ;
while( !frontier.empty() )
{
Top = frontier.top() ;
x = get<0>(Top) ;
y = get<1>(Top) ;
alreadyRemoved = get<2>(Top) ;
int val = littleQry( x , am , k[i] , y ) - alreadyRemoved;
if( tot + val > k[i] ) break ;
tot += val ;
am = x ;
frontier.pop() ;
}
if( frontier.empty() && tot < k[i] ) { ok = false ; break ; }
if( frontier.empty() )
{
frontier.push( make_tuple(x-1,y, 0) ) ;
continue;
}
int l = x+1 , r = am , mid , best = x ;
while( l <= r )
{
mid = (l+r)/2 ;
int val = littleQry( mid , am , k[i] , y ) ;
if( tot + val < k[i] ) r = mid -1 ;
else
{
best = mid ;
l = mid+1 ;
}
}
int val = littleQry(best, best,k[i], y ) ;
x = best ;
alreadyRemoved = max( 0 , val - tot ) ;
frontier.push(make_tuple(x,y,alreadyRemoved)) ;
}
return ok ;
}
/* //Delete after usage
int n , q ;
int a[MAXN] , b[MAXN] , k[MAXS] ;
int main()
{
scanf("%d", &n );
lp(i,0,n) scanf("%d%d", &a[i] , &b[i]) ;
init(n,a,b) ;
scanf("%d", &q) ;
lp(i,0,q)
{
int x ;
scanf("%d", &x) ;
lp(j,0,x) scanf("%d", &k[j]) ;
cout<<can(x,k)<<endl ;
}
} */
