#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define popb pop_back
using pii=pair<int,int>;
struct Node{
int val;
Node*l,*r;
Node():val(0),l(0),r(0){}
Node(int VAL):val(VAL),l(0),r(0){}
Node(Node*L,Node*R):val((L?L->val:0)+(R?R->val:0)),l(L),r(R){}
};
using pnode=Node*;
int getval(pnode p){
if(p)return p->val;
return 0;
}
pnode getl(pnode p){
if(p)return p->l;
return 0;
}
pnode getr(pnode p){
if(p)return p->r;
return 0;
}
pnode root[500100];
int n,*a,*b;
int P;
pnode update(int l,int r,pnode p){
if(l==r)return new Node(getval(p)+1);
int mid=(l+r)>>1;
if(P<=mid)return new Node(update(l,mid,getl(p)),getr(p));
return new Node(getl(p),update(mid+1,r,getr(p)));
}
pnode update(int x,pnode p){
P=x;
return update(0,n+5,p);
}
int L,R;
int query(int l,int r,pnode p){
if(!p)return 0;
if(L<=l&&r<=R)return p->val;
if(r<L||R<l)return 0;
int mid=(l+r)>>1;
return query(l,mid,p->l)+query(mid+1,r,p->r);
}
int query(int x,int y,int l,int r){
assert(x<=y);
L=l,R=r;
return query(0,n+5,root[y])-query(0,n+5,root[x-1]);
}
int cnt;
int getkth(int l,int r,pnode p,pnode q){
if(l==r)return l;
int mid=(l+r)>>1;
int lcnt=getval(getl(q))-getval(getl(p));
if(cnt<=lcnt){
return getkth(l,mid,getl(p),getl(q));
}
cnt-=lcnt;
return getkth(mid+1,r,getr(p),getr(q));
}
int getkth(int x,int y,int k){
assert(x<=y);
cnt=k;
return getkth(0,n+5,root[x-1],root[y]);
}
void init(int N, int A[], int B[]) {
n=N,a=A,b=B;
int p[N];
for(int i=0;i<n;i++){
p[i]=i;
}
sort(p,p+n,[&](int i,int j)->bool {
return a[i]<a[j];
});
int j=0;
for(int i=1;i<=n;i++){
root[i]=root[i-1];
while(j<n&&a[p[j]]==i){
root[i]=update(b[p[j]],root[i]);
j++;
}
}
}
struct state{
int h,end,cnt;
state(){}
state(int H,int END,int CNT):h(H),end(END),cnt(CNT){}
};
int can(int M, int K[]) {
long long ccnt=0;
for(int i=0;i<M;i++){
ccnt+=K[i];
}
if(n<ccnt)return 0;
sort(K,K+M);
vector<state>st;
st.pb({0,n,0});
st.pb({K[0],K[0]-1,query(1,K[0],0,K[0]-1)});
for(int i=0;i<M;i++){
int need=K[i];
while(need){
int sz=st.size();
if(sz==1)return 0;
state cur=st[sz-1],past=st[sz-2];
int all=getval(root[cur.h])-getval(root[past.h]);
int coulduse=query(past.h+1,cur.h,0,past.end)-cur.cnt;
if(need<coulduse){
cur.cnt+=need;
if(cur.cnt<all)cur.end=getkth(past.h+1,cur.h,cur.cnt+1)-1;
else {
cur.end=past.end;
}
if(past.end<=cur.end){
cur.end=past.end;
cur.cnt+=past.cnt;
st.pop_back();
}
st.back()=cur;
need=0;
}else{
cur.cnt+=coulduse+past.cnt;
cur.end=past.end;
st.popb();
st.back()=cur;
need-=coulduse;
}
}
if(i+1<M){
int nx=K[i+1];
if(st.back().h==nx)continue;
while(st.back().end<nx-1){
st.popb();
}
state cur=state(nx,nx-1,query(st.back().h+1,nx,0,nx-1));
if(st.back().end==cur.end){
cur.cnt+=st.back().cnt;
st.popb();
}
st.pb(cur);
}
}
return 1;
}
