#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)101*1000)
#define K ((int)22)
#define SQ ((int)500)
int n,pos[N];
pair <int,int> a[N];
int seg[K][N];
void build(int xl=0,int xr=n,int h=0)
{
if(xl==xr-1)
{
seg[h][xl]=a[xl].second;
return ;
}
int mid=(xl+xr)/2;
build(xl,mid,h+1);
build(mid,xr,h+1);
merge(seg[h+1]+xl,seg[h+1]+mid,seg[h+1]+mid,seg[h+1]+xr,seg[h]+xl);
}
int query(int q,int val,int xl=0,int xr=n,int h=0)
{
if(xr<=q)return xr-(lower_bound(seg[h]+xl,seg[h]+xr,val)-seg[h]);
int mid=(xl+xr)/2;
int res=query(q,val,xl,mid,h+1);
if(mid<q)res+=query(q,val,mid,xr,h+1);
return res;
}
void init(int n2, int A[], int B[])
{
n=n2;
for(int i=0;i<n;i++)a[i]={A[i],B[i]};
sort(a,a+n);
for(int i=1,j=0;i<=n;i++)
{
while(j<n && a[j].first<=i)j++;
pos[i]=j;
}
build();
}
pair <int,int> b[N];
int cnt[SQ][SQ];
int can(int m, int k[])
{
int m2=0,sum=0;
sort(k,k+m);
for(int i=0;i<m;i++)sum+=k[i];
if(sum>n)return 0;
for(int i=0;i<m;)
{
b[m2]={k[i],0};
while(i<m && k[i]==b[m2].first)b[m2].second+=k[i],i++;
m2++;
}
m=m2;
for(int i=0;i<m;i++)
for(int j=i;j<m;j++)
cnt[i][j]=query(pos[b[i].first],b[j].first);
for(int i=m-1;i>=0;i--)
for(int j=i;j<m;j++)
cnt[i][j]+=-((j<m-1)?cnt[i][j+1]:0)-((i>0)?cnt[i-1][j]:0)+((i>0 && j<m-1)?cnt[i-1][j+1]:0);
for(int i=0;i<m;i++)
{
for(int j=i;j<m && b[i].second;j++)
{
int x=min(b[i].second,cnt[i][j]);
b[i].second-=x;
cnt[i][j]-=x;
}
if(b[i].second)return 0;
for(int j=0;j<m;j++)cnt[i+1][j]+=cnt[i][j];
}
return 1;
}
