#include "teams.h"
#include <bits/stdc++.h>
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n;
vector<int> v[500005];
struct node
{
int sum=0;
node *l,*r;
void up()
{
sum=l->sum+r->sum;
}
}*root[1000005],*ti[500005];
void build(int l,int r,node *&p)
{
p=new node;
if(l==r)
return;
int m=l+r>>1;
build(l,m,p->l),build(m+1,r,p->r);
}
node *modify(int x,int l,int r,node *p,int v)
{
p=new node(*p);
if(l==r)
return p->sum+=v,p;
int m=l+r>>1;
if(x<=m) p->l=modify(x,l,m,p->l,v);
else p->r=modify(x,m+1,r,p->r,v);
return p->up(),p;
}
node *modify2(int x,int l,int r,node *p,int v)
{
p=new node(*p);
if(l==r)
return p->sum=v,p;
int m=l+r>>1;
if(x<=m) p->l=modify2(x,l,m,p->l,v);
else p->r=modify2(x,m+1,r,p->r,v);
return p->up(),p;
}
int cunt(int x,int l,int r,node *p)
{
if(l==r) return 0;
int m=l+r>>1;
if(x<=m) return cunt(x,l,m,p->l);
return p->l->sum+cunt(x,m+1,r,p->r);
}
void init(int N, int A[], int B[])
{
n=N;
for(int i=0;i<N;++i)
v[A[i]].pb(B[i]);
int tp=0;
build(1,N,root[tp]);
for(int i=1;i<=N;++i)
{
for(int j:v[i])
root[tp+1]=modify(j,1,n,root[tp],1),++tp;
if(i>1) root[tp+1]=modify2(i-1,1,n,root[tp],0),++tp;
ti[i]=root[tp];
}
}
int can(int M, int K[])
{
ll ned=0,pre=0,cnt;
vector<ll> query;
for(int i=0;i<M;++i)
query.pb(K[i]);
sort(ALL(query));
for(int i=0;i<M;++i)
{
ned+=query[i];
if(ti[query[i]]->sum+pre<ned) return 0;
if(i+1<M)
{
cnt=cunt(query[i+1],1,n,ti[query[i]]);
if(cnt>=ned-pre)
pre=ned;
else
pre=cnt;
}
}
return 1;
}
