#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 1e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "teams.h"
vector < int > v[ N ] , v1[ N ] ;
int n ;
int cc = 2 ;
int node[ 12 * N ] ;
pair < int , int > p[ 12 * N ] ;
void build( int v , int vl , int vr ){
if( vl == vr ){
node[ v ] = 0 ;
return ;
}
int vm = ( vl + vr ) / 2 ;
p[ v ].f = cc ; cc ++ ;
p[ v ].s = cc ; cc ++ ;
build( p[ v ].f , vl , vm ) ;
build( p[ v ].s , vm + 1 , vr ) ;
return ;
}
int app[ N ] ;
void update( int v , int old , int vl , int vr , int pos , int val ){
if( vl == vr ){
node[ v ] = node[ old ] + val ;
return ;
}
int vm = ( vl + vr ) / 2 ;
if( vm >= pos ){
p[ v ].s = p[ old ].s ;
p[ v ].f = cc ; cc ++ ;
update( p[ v ].f , p[ old ].f , vl , vm , pos , val ) ;
}
else{
p[ v ].f = p[ old ].f ;
p[ v ].s = cc ; cc ++ ;
update( p[ v ].s , p[ old ].s , vm + 1 , vr , pos , val ) ;
}
node[ v ] = node[ p[ v ].f ] + node[ p[ v ].s ] ;
return ;
}
int get( int v , int vl , int vr , int l , int r ){
if( l > r ) return 0 ;
if( vl == l && vr == r ){
return node[ v ] ;
}
int vm = ( vl + vr ) / 2 ;
int a = get( p[ v ].f , vl , vm , l , min( r , vm ) ) ;
int b = get( p[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
return a + b ;
}
map < int , int > pp[ N ] ;
void init(int n1, int A[], int B[]){
n = n1 ;
FOR( i , n ){
v[ A[ i ] ].pb( B[ i ] ) ;
pp[ A[ i ] ][ B[ i ] ] ++ ;
}
build( 1 , 1 , n ) ;
app[ 0 ] = 1 ;
for( int j = 1 ; j <= n ; j ++ ){
int lst = app[ j - 1 ] ;
for( auto x : pp[ j ] ){
cc ++ ;
int ls = cc - 1 ;
update( cc - 1 , lst , 1 , n , x.f , x.s ) ;
lst = ls ;
}
app[ j ] = lst ;
}
}
int sm[ N ] ;
int gaq[ N ] ;
int ginda[ N ] ;
set < int > se ;
map < pair < int , int > , int > mu ;
map < int , int > hs ;
int pipi[ N ] ;
int can(int M, int K[]){
sort( K , K + M ) ;
int smm =0 ;
hs.clear() ;
FOR( i , M ) smm += K[ i ] ;
if( smm > n ) return 0 ;
se.clear() ;
se.insert( n + 1 ) ;
int titu = 0 ;
FOR( i , M ){
se.insert( K[ i ] ) ;
hs[ K[ i ] ] = 1 ;
sm[ K[ i ] ] = 0 ;
}
int cc = 0 ;
for( auto x : se ){
pipi[ titu ] = x ; titu ++ ;
gaq[ x ] = cc ;
ginda[ cc ] = x ;
cc ++ ;
}
ginda[ cc ] = INT_MAX ;
se.insert( INT_MAX ) ;
int tt = 1 ;
FOR( i , M ){
int x = K[ i ] ;
int rt = app[ x ] ;
int l = 0 , r = se.size() - 1 ;
mu.clear() ;
while( l <= r ){
mu[ { l , r } ] ++ ;
if( mu[ { l , r } ] == 2 ) break ;
int mid = ( l + r ) / 2 ;
int md = mid ;
mid = pipi[ mid ] - 1 ;
int sum = get( rt , 1 , n , x , mid ) ;
int pp = x ;
while( true ){
sum -= sm[ pp ] ;
pp = ginda[ 1 + gaq[ pp ] ] ;
if( pp > mid ) break ;
}
if( sum < x ){
l = md + 1 ;
}
else r = md ;
}
if( l > r ){
tt = 0 ; break ;
}
l = pipi[ l ] ;
int pp = x , ls = x , lf = x ;
while( true ){
int nx = min( l + 1 , ginda[ 1 + gaq[ pp ] ] ) ;
int xx = get( rt , 1 , n , pp , nx - 1 ) - sm[ pp ] ;
// if( nx == l + 1 ){
// xx = lf ;
// } else lf -= xx ;
sm[ pp ] += xx ;
pp = ginda[ 1 + gaq[ pp ] ] ;
if( pp > l ) break ;
}
}
return tt ;
}
//static char buffer[1024];
//static int currentChar = 0;
//static int charsNumber = 0;
//
//
//
//int main() {
// int N;
// cin >> N ;
// int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
// int *B = (int *)malloc(sizeof(int) * (unsigned int)N);
// for (int i = 0; i < N; ++i) {
// cin >> A[ i ] ;
// cin >> B[ i ] ;
// }
// init(N, A, B);
// int Q;
// cin >> Q ;
// for (int i = 0; i < Q; ++i) {
// int M;
// cin >> M ;
// int *K = (int *)malloc(sizeof(int) * (unsigned int)M);
// for (int j = 0; j < M; ++j) {
// cin >> K[ j ] ;
// }
// cout << can( M , K ) << "\n" ;
// }
// return 0;
//}
