#include <bits/stdc++.h>
using namespace std;
typedef long long int llo;
#define a first
#define b second
#define pb push_back
#define mp make_pair
#include "teams.h"
int n;
int aa[500001];
int bb[500001];
vector<int> su[500001];
int tree[30*500001];
int l[30*500001];
int r[30*500001];
int root=0;
int dp[500001];
int lab[500001];
int cnt=0;
vector<int> xx[500001];
void build(int no,int ll,int rr){
cnt=max(cnt,no);
if(ll==rr){
tree[no]=0;
}
else{
int mid=(ll+rr)/2;
build(no*2+1,ll,mid);
build(no*2+2,mid+1,rr);
tree[no]=0;
l[no]=no*2+1;
r[no]=no*2+2;
}
}
int update(int no,int ll,int rr,int ind){
if(ll==rr){
cnt++;
tree[cnt]=tree[no]+1;
return cnt;
}
else{
int mid=(ll+rr)/2;
cnt++;
int cur=cnt;
if(ind<=mid){
l[cur]=update(l[no],ll,mid,ind);
r[cur]=r[no];
}
else{
r[cur]=update(r[no],mid+1,rr,ind);
l[cur]=l[no];
}
tree[cur]=tree[l[cur]]+tree[r[cur]];
return cur;
}
}
void init(int nn, int A[], int B[]) {
n=nn;
for(int i=0;i<n;i++){
aa[i]=A[i];
bb[i]=B[i];
su[bb[i]].pb(aa[i]);
xx[aa[i]].pb(bb[i]);
}
build(0,0,n-1);
for(int i=n;i>=1;i--){
for(auto j:su[i]){
root=update(root,0,n-1,j-1);
}
lab[i]=root;
}
}
int query(int no,int ll,int rr,int aa,int bb){
if(rr<aa or ll>bb or aa>bb){
return 0;
}
if(aa<=ll and rr<=bb){
//cout<<ll<<"..."<<rr<<endl;
return tree[no];
}
else{
int mid=(ll+rr)/2;
return query(l[no],ll,mid,aa,bb)+query(r[no],mid+1,rr,aa,bb);
}
}
int can(int m, int k[]){
if(m>300){
int so=0;;
for(int i=0;i<m;i++){
xx[k[i]].pb(n+1);
so+=k[i];
}
if(so>n){
return 0;
}
priority_queue<int> cur;
for(int i=1;i<=n;i++){
for(auto j:xx[i]){
if(j==n+1){
while(cur.size() and -cur.top()<i){
cur.pop();
}
for(int kk=0;kk<i;kk++){
if(cur.size()==0){
for(int ii=0;ii<m;ii++){
xx[k[ii]].pop_back();
}
return 0;
}
cur.pop();
}
}
else{
cur.push(-j);
}
}
}
for(int i=0;i<m;i++){
xx[k[i]].pop_back();
}
return 1;
}
sort(k,k+m);
for(int i=0;i<m;i++){
dp[i]=query(lab[k[i]],0,n-1,0,k[i]-1)-k[i];
for(int j=0;j<i;j++){
dp[i]=min(dp[i],dp[j]+query(lab[k[i]],0,n-1,k[j],k[i]-1)-k[i]);
}
if(dp[i]<0){
return 0;
}
}
return 1;
}
