#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=500050;
const int M=40*N;
//namespace ST{
// int root,ls[M],rs[M],st[M],tsz;
// void Set(int&c,int ss,int se,int qs,int qe,int x){
// if(!c)c=++tsz;
// if(ss>qe||se<qs)return;
// if(qs<=ss&&se<=qe){st[c]=x;return;}
// int mid=ss+se>>1;
// Set(ls[c],ss,mid,qs,qe,x);
// Set(rs[c],mid+1,se,qs,qe,x);
// }
// int Get(int c,int ss,int se,int qi){
// if(ss==se)return st[c];
// int mid=ss+se>>1;
// if(qi<=mid)return max(st[c],Get(ls[c],ss,mid,qi));
// else return max(st[c],Get(rs[c],mid+1,se,qi));
// }
//}
int n,ls[M],rs[M],st[M],root[N],tsz;
void Set(int&c,int p,int ss,int se,int qi,int x){
c=++tsz;ls[c]=ls[p];rs[c]=rs[p];st[c]=st[p]+x;
if(ss==se)return;
int mid=ss+se>>1;
if(qi<=mid)Set(ls[c],ls[p],ss,mid,qi,x);
else Set(rs[c],rs[p],mid+1,se,qi,x);
}
int Get(int c,int p,int ss,int se,int qs,int qe){
if(qs>qe||ss>qe||se<qs)return 0;
if(qs<=ss&&se<=qe)return st[c]-st[p];
int mid=ss+se>>1;
return Get(ls[c],ls[p],ss,mid,qs,qe)+Get(rs[c],rs[p],mid+1,se,qs,qe);
}
vector<int> Qs[N];
void init(int N,int A[],int B[]) {
n=N;
for(int i=0;i<n;i++)Qs[A[i]].pb(B[i]);
for(int i=1;i<=n;i++){
root[i]=root[i-1];
for(int x:Qs[i])Set(root[i],root[i],1,n,x,1);
}
}
int cnt[N];
int can(int M,int K[]) {
ll s=0;
for(int i=0;i<M;i++)s+=K[i];
if(s>n)return 0;
vector<int> val;
for(int i=0;i<M;i++)val.pb(K[i]),cnt[K[i]]++;
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
int sz=val.size(),nroot=++tsz;
vector<ll> rem(sz);
for(int i=0;i<sz;i++){
int v=val[i];
ll need=(ll)v*cnt[v];
for(int j=i;j<sz;j++){
int nxt=(j==sz-1?n:val[j+1]-1);
ll x=min(need,Get(root[v],nroot,1,n,val[j],nxt)-rem[j]);
need-=x; rem[j]+=x;
if(need==0)break;
//Set(nroot,1,n,val[j],);
}
if(need>0){
for(int x:val)cnt[x]=0;
return 0;
}
}
for(int x:val)cnt[x]=0;
return 1;
}
