#include <bits/stdc++.h>
#include "teams.h"
#define debug
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int, int>
#define mkt make_tuple
const int MAXN = 5e5+10 , MAX = 1e6+10 ;
using namespace std ;
struct Seg
{
vector<int> e , d , soma ;
int m(int l, int r) { return (l+r)>>1 ; }
int create()
{
e.pb( 0 ) ;
d.pb( 0 ) ;
soma.pb( 0 ) ;
return (int)(e.sz) - 1 ;
}
int create_and_copy(int pos)
{
e.pb( e[pos] ) ;
d.pb( d[pos] ) ;
soma.pb( soma[pos] ) ;
return (int)(e.sz) - 1 ;
}
int upd(int pos, int l, int r, int idx )
{
int novo = create_and_copy(pos) ;
if( l == r )
{
soma[novo] ++ ;
return novo ;
}
int aux ;
if( idx <= m(l,r) )
{
aux = upd(e[novo] , l, m(l,r) , idx ) ;
e[novo] = aux ;
}
else
{
aux = upd(d[novo] ,m(l,r)+1, r , idx ) ;
d[novo] = aux ;
}
soma[novo] = soma[ e[novo] ] + soma[ d[novo] ] ;
return novo ;
}
int bbp(int v1, int v2, int l, int r, int& val )
{
if( l == r )
{
val -= soma[v2] - soma[v1] ;
return l ;
}
int aux = soma[ e[v2] ] - soma[ e[v1] ] ;
if( aux >= val )
return bbp( e[v1] , e[v2] , l , m(l,r) , val ) ;
val -= aux ;
return bbp( d[v1] , d[v2] , m(l,r)+1, r, val ) ;
}
int qry(int pos, int l, int r, int beg, int en)
{
if( l > en || r < beg ) 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 ;
}
void print(int pos, int l, int r)
{
if( l == r ) return (void)( printf("%d ", soma[pos]) ) ;
print(e[pos] , l, m(l,r)) ;
print(d[pos],m(l,r)+1, r) ;
}
} ;
//Declarations
int n , q , m , cnt = 1 ;
int A[MAXN] , B[MAXN] , version[MAX] , isThere[MAX+5] ;
vector< tuple<int,int,int> > littleCompr , untitled ;
Seg seg ;
int find(int val, int t)
{
//T == 0 -> procura o menor de todos cuja compressao eh maior ou igual a val
//T == 1 -> procura o maior de todos cuja compressao eh menor ou igual a val
int l = 0 , r = (int)( littleCompr.sz ) - 1 , mid , best=0;
if( t == 0 && get<0>(littleCompr[r]) < val ) return -1 ;
while( l <= r )
{
mid = (l+r)>>1 ;
if( t == 0 )
{
if( get<0>(littleCompr[mid]) >= val )
{
best = mid ;
r = mid - 1 ;
}
else l = mid + 1 ;
}
else
{
if( get<0>(littleCompr[mid]) <= val )
{
best = mid ;
l = mid+1 ;
}
else r = mid -1 ;
}
}
return best + 1 ;
}
bool processQuery()
{
stack< tuple<int,int,int> > pilha ;
sort( all(untitled) ) ;
// begL , enL , limR
pilha.push( mkt( 0 , 0 , MAX ) ) ;
bool isPossible = true ;
for(auto p : untitled )
{
int x = get<0>(p) , y = get<1>(p) , val = get<2>(p) ;
int fineLine = y ;
while( val )
{
//printPile() ;
if( pilha.sz == 0 )
{
isPossible = false ;
break ;
}
tuple<int,int,int> cur = pilha.top() ;
int enL = get<1>(cur) , limR = get<2>(cur) ;
if( limR < fineLine )
{
pilha.pop() ;
continue ;
}
val += seg.qry( version[x] , 0 , MAX , 0,fineLine-1 ) - seg.qry(version[enL] , 0 , MAX ,0, fineLine-1 ) ;
int couldBe = seg.qry( version[x] , 0 , MAX , 0,limR ) - seg.qry( version[enL] , 0 ,MAX , 0,limR ) ;
if( val > couldBe )
{
pilha.pop() ;
fineLine = limR+1 ;
val -= couldBe ;
continue ;
}
fineLine = seg.bbp( version[ enL ] , version[ x ] , 0 , MAX , val ) ;
pilha.push( mkt( enL , x , fineLine ) ) ;
}
if( !isPossible ) break ;
}
return isPossible ;
}
void init(int N, int a[], int b[]) {
seg.create() ;
n = N ;
lp(i,1,n+1) A[i] = a[i-1] , B[i] = b[i-1] ;
//Little compression
//This way, nobody will have the same R
//Makes life easier
lp(i,1,n+1)
{
littleCompr.pb( mkt( A[i] , 0 , i ) ) ;
littleCompr.pb( mkt( B[i] , 1 , i ) ) ;
}
sort( littleCompr.begin() , littleCompr.end() ) ;
for(auto p : littleCompr )
{
int type = get<1>(p) , id = get<2>(p) ;
int& ref = ( type == 0 ? A[id] : B[id] ) ;
ref = cnt ++ ;
if( type == 0 ) isThere[ref] = id ;
}
//Updating the segment tree
for(int i = 1 ; i <= MAX ; i++ )
{
if( isThere[i] == 0 )
{
version[i] = version[i-1] ;
continue ;
}
version[i] = seg.upd( version[i-1] , 0 , MAX , B[ isThere[i] ] ) ;
}
}
int can(int M, int K[]) {
m = M ;
untitled.clear() ;
bool cantAlready = false ;
lp(i,0,m)
{
int x = K[i];
int l = find(x,1);
int r = find(x,0) ;
if( r == -1 ) cantAlready = true ;
untitled.pb( mkt( l , r , x ) ) ;
}
m = (int)( untitled.sz ) ;
if( cantAlready ) return 0 ;
return processQuery() ;
}
