#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 = 2e6 + 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 dp[ N ] , k[ N ] , bn[ N ] ;
int get_when( int x , int y ){
if( k[ x ] == k[ y ] ) return INT_MAX ;
int l = k[ y ] , r = n + 1 ;
while( l < r ){
int mid = ( l + r ) / 2 ;
if( mid == n + 1 ) return INT_MAX ;
int aa = get( app[ mid ] , 1 , n , mid , n ) - get( app[ k[ x ] ] , 1 , n , mid , n ) ;
int bb = get( app[ mid ] , 1 , n , mid , n ) - get( app[ k[ y ] ] , 1 , n , mid , n ) ;
int a = dp[ x ] + aa ;
int b = dp[ y ] + bb ;
if( a <= b ){
r = mid ;
}
else l = mid + 1 ;
}
if( l > r ) l = INT_MAX ;
return l ;
}
int opa( int x , int y ){
int cc = 0 ;
if( x != -1 )
cc = get( app[ k[ x ] ] , 1 , n , k[ y ] , n ) ;
int aa = get( app[ k[ y ] ] , 1 , n , k[ y ] , n ) - cc ;
int cic = 0 ;
if( x != -1 ) cic = dp[ x ] ;
int a = cic + aa ;
a -= k[ y ] ;
return a ;
}
int can(int M, int K[]){
sort( K , K + M ) ;
FOR( i , M ) k[ i ] = K[ i ] , bn[ i ] = 0 , dp[ i ] = 0 ;
int smm =0 ;
FOR( i , M ) smm += K[ i ] ;
if( smm > n ) return 0 ;
set < int > se ;
set < pair < int , pair < int , int > > > lst ;
int mn = INT_MAX ;
FOR( i , M ){
int x = k[ i ] ;
while( true ){
pair < int , pair < int , int > > p ;
if( lst.size() == 0 ) break ;
p = *(lst.begin()) ;
if( p.f > k[ i ] ) break ;
lst.erase( lst.begin() ) ;
if( bn[ p.s.s ] == 1 ) continue ;
if( bn[ p.s.f ] == 1 ) continue ;
bn[ p.s.f ] = 1 ;
se.erase( se.find( p.s.f ) ) ;
if( se.size() == 0 ) break ;
if( *( -- se.end() ) != p.s.s ){
int x = p.s.s ;
int y = *se.upper_bound( x ) ;
int tm = get_when( x , y ) ;
lst.insert( { tm , { y , x } } ) ;
}
}
int X , Y ;
if( se.size() == 0 ){
X - -1 , Y = i ;
dp[ i ] = opa( -1 , i ) ;
}
else{
int cc = *( --se.end() ) ;
dp[ i ] = min( opa( cc, i ) , opa( -1 , i ) ) ;
X = *(--se.end() ) ;
Y = i ;
}
// cout << i << " " << dp[ i ] << endl ;
if( se.size() != 0 ){
int x = *(--se.end() ) ;
int y = i ;
int tm = get_when( x , y ) ;
lst.insert( { tm , { y , x } } ) ;
}
se.insert( i ) ;
mn = min( mn , dp[ i ] ) ;
// cout << i << " " << K[ i ] << " " << dp[ i ] << " " << X << " " << Y << endl ;
}
if( mn < 0 ) return 0 ;
return 1 ;
}
//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;
//}
