#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "teams.h"
using namespace std;
struct Persistent
{
Persistent *l,*r;
int sum=0;
void comp() { sum=l->sum+r->sum; }
} *ver[500005];
Persistent *build(Persistent *u,int l,int r)
{
u=new Persistent();
if(l==r) return u;
int mid=(l+r)>>1;
u->l=build(u->l,l,mid); u->r=build(u->r,mid+1,r);
return u;
}
Persistent *update(Persistent *u,int l,int r,int x)
{
Persistent *v=new Persistent();
v->l=u->l;
v->r=u->r;
v->sum=u->sum;
if(l==r) v->sum++;
else
{
int mid=(l+r)>>1;
if(x<=mid) v->l=update(u->l,l,mid,x);
else v->r=update(u->r,mid+1,r,x);
v->comp();
}
return v;
}
int st[4*500005];
Persistent *lz[4*500005];
void change(int id,Persistent *x)
{
lz[id]=x;
st[id]=x->sum;
}
void down(int id)
{
Persistent *x=lz[id];
if(x==NULL) return ;
change(id*2,x->l); change(id*2+1,x->r);
lz[id]=NULL;
}
void updateIT(int id,int l,int r,int u,int v,Persistent *x)
{
if(u>r || v<l) return ;
if(u<=l && r<=v) { change(id,x); return ; }
down(id);
int mid=(l+r)>>1;
updateIT(id*2,l,mid,u,v,x->l); updateIT(id*2+1,mid+1,r,u,v,x->r);
st[id]=st[id*2]+st[id*2+1];
}
int getIT(int id,int l,int r,int u,int v,Persistent *x)
{
if(u>r || v<l) return 0;
if(u<=l && r<=v) return x->sum-st[id];
down(id);
int mid=(l+r)>>1;
return getIT(id*2,l,mid,u,v,x->l)+getIT(id*2+1,mid+1,r,u,v,x->r);
}
int Find(int id,int l,int r,Persistent *x,int k)
{
if(l==r) return l;
down(id);
int mid=(l+r)>>1,t=x->l->sum-st[id*2];
if(t>=k) return Find(id*2,l,mid,x->l,k);
return Find(id*2+1,mid+1,r,x->r,k-t);
}
int n,m,i,a[500005],b[500005],cnt,Endn[500005],q,inST[500005],Begin[500005];
vector <int> vec[500005];
void init(int _n,int _a[],int _b[])
{
n=_n;
vector <II> VecB;
for(i=0;i<n;i++) VecB.push_back({ _b[i],i });
sort(VecB.begin(),VecB.end());
for(II x:VecB)
{
inST[x.snd]=++cnt;
if(Begin[x.fst]==0) Begin[x.fst]=cnt;
}
for(i=n;i>=1;i--)
if(Begin[i]==0) Begin[i]=Begin[i+1];
cnt=0;
for(i=0;i<n;i++) vec[_a[i]].push_back(inST[i]);
ver[0]=build(ver[0],1,n);
for(i=1;i<=n;i++)
{
for(int x:vec[i]) cnt++,ver[cnt]=update(ver[cnt-1],1,n,x);
Endn[i]=cnt;
}
}
int can(int m,int _a[])
{
for(i=m;i>=1;i--) a[i]=_a[i-1];
sort(a+1,a+m+1);
updateIT(1,1,n,1,n,ver[0]);
for(i=1;i<=m;i++)
{
Persistent *u=ver[Endn[a[i]]];
if(Begin[a[i]]==0) return 0;
int k=getIT(1,1,n,1,Begin[a[i]]-1,u);
if(getIT(1,1,n,1,n,u)<a[i]+k)
return 0;
int pos=Find(1,1,n,u,a[i]+k);
updateIT(1,1,n,Begin[a[i]],pos,u);
}
return 1;
}
/*
int main()
{
freopen("teams.inp","r",stdin);
freopen("teams.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(i=0;i<n;i++) cin>>a[i]>>b[i];
init(n,a,b);
cin>>q;
while(q--)
{
cin>>m;
for(i=0;i<m;i++) cin>>a[i];
cout<<can(m,a)<<'\n';
}
}
*/
