#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
int n,sz;
vector<int>G[500005];
struct PST{
int l,r,val;
}T[11000000];
int root[500005];
void initree(int num,int s,int e)
{
if(s==e)return ;
T[num].l=sz;
T[sz++]={-1,-1,0};
T[num].r=sz;
T[sz++]={-1,-1,0};
initree(T[num].l,s,(s+e)/2);
initree(T[num].r,(s+e)/2+1,e);
}
void update(int par,int num,int s,int e,int x)
{
T[num].val=T[par].val+1;
if(s==e)return ;
if(x<=(s+e)/2)
{
T[num].r=T[par].r;
T[num].l=sz;
T[sz++]={-1,-1,0};
update(T[par].l,T[num].l,s,(s+e)/2,x);
}
else
{
T[num].l=T[par].l;
T[num].r=sz;
T[sz++]={-1,-1,0};
update(T[par].r,T[num].r,(s+e)/2+1,e,x);
}
}
struct D{
int A,B;
}d[500005];
int go[500005];
bool cmp(D a,D b){return a.B<b.B;}
void init(int N, int A[], int B[]) {
n=N;
for(int i=0;i<n;i++)
{
d[i]={A[i],B[i]};
go[i+1]=1e9;
}
sort(d,d+n,cmp);
for(int i=0;i<n;i++)
{
go[d[i].B]=min(go[d[i].B],i+1);
G[d[i].A].push_back(i+1);
}
for(int i=n-1;i>=1;i--)go[i]=min(go[i],go[i+1]);
root[0]=sz;
T[sz++]={-1,-1,0};
initree(0,1,n);
for(int i=1;i<=n;i++)
{
if(!sz(G[i]))
{
root[i]=root[i-1];
continue;
}
int prev=root[i-1];
for(auto &k:G[i])
{
root[i]=sz;
T[sz++]={-1,-1,0};
update(prev,root[i],1,n,k);
prev=root[i];
}
}
}
int getsum(int num1,int num2,int s,int e,int x1,int x2)
{
if(s>x2||x1>e)return 0;
if(x1<=s&&e<=x2)return T[num2].val-T[num1].val;
return getsum(T[num1].l,T[num2].l,s,(s+e)/2,x1,x2)+getsum(T[num1].r,T[num2].r,(s+e)/2+1,e,x1,x2);
}
int getx(int x1,int x2,int y1,int y2)
{
return getsum(root[y1-1],root[y2],1,n,x1,x2);
}
int rem[200002];
int can(int M, int K[]) {
lint sum=0;
for(int i=0;i<M;i++)sum+=K[i];
if(sum>n)return 0;
int ans=1,t;
sort(K,K+M);
t=K[0];
vector<pii>V;
for(int i=1;i<M;i++)
{
if(K[i]==K[i-1])
{
t+=K[i];
}
else
{
V.push_back({K[i-1],t});
t=K[i];
}
}
V.push_back({K[M-1],t});
int m=sz(V);
for(int i=0;i<m;i++)rem[i]=V[i].second;
for(int i=m-1;i>=0;i--)
{
int r=0;
for(int j=m-1;j>=i+1;j--)
{
if(!rem[j])continue;
t=getx(go[V[j].first],n,i==0?1:(V[i-1].first+1),V[i].first)-r;
if(rem[j]<t)t=rem[j];
r+=t;
rem[j]-=t;
}
t=getx(go[V[i].first],n,i==0?1:(V[i-1].first+1),V[i].first)-r;
if(rem[i]<t)t=rem[i];
rem[i]-=t;
}
for(int i=0;i<m;i++)if(rem[i])ans=0;
return ans;
}
