#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[8*500001];
int l[8*500001];
int r[8*500001];
int root=0;
int dp[500001];
int lab[500001];
int cnt=0;
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;
//cout<<ll<<"<<"<<tree[cnt]<<endl;
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]);
}
//cout<<22<<endl;
build(0,0,n-1);
for(int i=n;i>=1;i--){
for(auto j:su[i]){
// cout<<i<<":"<<j<<endl;
root=update(root,0,n-1,j-1);
}
lab[i]=root;
//cout<<lab[i]<<"/"<<endl;
}
//cout<<endl;
//cout<<11<<endl;
}
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[]){
sort(k,k+m);
if(m>900){
vector<pair<int,int>> xx;
for(int i=0;i<n;i++){
xx.pb({aa[i],bb[i]});
}
for(int i=0;i<m;i++){
xx.pb({k[i],n+1});
}
sort(xx.begin(),xx.end());
multiset<int> cur;
for(auto j:xx){
if(j.b==n+1){
while(cur.size()){
if(*(cur.begin())<j.a){
cur.erase(cur.begin());
}
else{
break;
}
}
for(int k=0;k<j.a;k++){
if(cur.size()==0){
return 0;
}
cur.erase(cur.begin());
}
}
else{
cur.insert(j.b);
}
}
return 1;
}
if(true){
for(int i=0;i<m;i++){
//cout<<lab[k[i]]<<"::"<<0<<"::"<<k[i]-1<<endl;
//cout<<query(lab[k[i]],0,n-1,0,k[i]-1)<<endl;
dp[i]=query(lab[k[i]],0,n-1,0,k[i]-1)-k[i];
//cout<<dp[i]<<"::"<<endl;
for(int j=0;j<i;j++){
// cout<<query(lab[k[i]],0,n-1,k[j],k[i]-1)<<":"<<k[j]<<":"<<k[i]-1<<endl;
dp[i]=min(dp[i],dp[j]+query(lab[k[i]],0,n-1,k[j],k[i]-1)-k[i]);
}
// cout<<i<<"//"<<dp[i]<<",,"<<endl;
if(dp[i]<0){
return 0;
}
}
}
return 1;
}
