#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=500050;
const int M=20*N;
int n,ls[M],rs[M],tsz,root[N],sum[M];
void Set(int p, int &c, int ss, int se, int qi)
{
c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+1;
if(ss==se) return;
int mid=ss+se>>1;
if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
else Set(rs[p],rs[c],mid+1,se,qi);
}
int Get(int c, int ss, int se, int qs, int qe)
{
if(qs>se || ss>qe) return 0;
if(qs<=ss && qe>=se) return sum[c];
int mid=ss+se>>1;
return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
vector<int> all[N];
void init(int m, int a[], int b[])
{
n=m;int i,j;
for(i=0;i<n;i++) all[a[i]].pb(b[i]);
for(i=1;i<=n;i++)
{
root[i]=root[i-1];
for(j=0;j<all[i].size();j++) Set(root[i],root[i],1,n,all[i][j]);
}
}
int min(int a, int b){ return a>b?b:a;}
int val[N],cnt[N],used[N];
bool can(int m, int k[])
{
int sum=0,i,j,sz=0;
sort(k,k+m);
for(i=0;i<m;i++)
{
sum+=k[i];
if(sz && val[sz-1]==k[i]) cnt[sz-1]+=k[i];
else val[sz]=cnt[sz]=k[i],sz++;
}
if(sum>n) return 0;
m=sz;
for(i=0;i<=m;i++) used[i]=0;
val[m]=n+1;
for(i=0;i<m;i++)
{
int need=cnt[i];
int l=val[i];
for(j=i;j<m;j++)
{
int have=Get(root[l],1,n,val[j],val[j+1]-1)-used[j];
int add=min(have,need);
need-=add;
used[j]+=add;
if(!need) break;
}
if(need) return 0;
}
return 1;
}
