#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<"="<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define all(x) x.begin(), x.end()
#define pb push_back
const int MAXN=500010, SQ=250, SEGSZ=10000010;
int n, m, k, x, y;
int A[MAXN], B[MAXN], C[MAXN], root[MAXN];
int seg[SEGSZ], L[SEGSZ], R[SEGSZ], ts;
int ted[SQ][SQ], cnt[SQ];
priority_queue<int, vector<int>, greater<int>> pq;
int Add(int id, int tl, int tr, int pos){
if (pos<tl || tr<=pos) return id;
int res=++ts;
if (tr-tl==1){
seg[res]=seg[id]+1;
return res;
}
int mid=(tl+tr)>>1;
L[res]=Add(L[id], tl, mid, pos);
R[res]=Add(R[id], mid, tr, pos);
seg[res]=seg[L[res]]+seg[R[res]];
return res;
}
int Get(int idl, int idr, int tl, int tr, int l, int r){
if (r<=tl || tr<=l) return 0;
if (l<=tl && tr<=r) return seg[idr]-seg[idl];
int mid=(tl+tr)>>1;
return Get(L[idl], L[idr], tl, mid, l, r) + Get(R[idl], R[idr], mid, tr, l, r);
}
void init(int nn, int AA[], int BB[]){
n=nn;
vector<pii> vec;
for (int i=0; i<n; i++) vec.pb({AA[i], BB[i]});
sort(all(vec));
for (int i=0; i<n; i++) A[i+1]=vec[i].first, B[i+1]=vec[i].second;
int j=1;
for (int i=1; i<=n; i++){
root[i]=root[i-1];
while (A[j]==i) root[i]=Add(root[i], 1, n+1, B[j++]);
}
}
bool SolveBig(){
while (pq.size()) pq.pop();
int j=1;
for (int i=1; i<=m; i++){
while (j<=n && A[j]<=C[i]) pq.push(B[j++]);
while (pq.size() && pq.top()<C[i]) pq.pop();
int t=C[i];
if (pq.size()<t) return 0;
while (t--) pq.pop();
}
return 1;
}
bool SolveSmall(){
C[m+1]=n+1;
for (int i=1; i<=m; i++) for (int j=i; j<=m; j++)
ted[i][j]=Get(root[C[i-1]], root[C[i]], 1, n+1, C[j], C[j+1]);
for (int i=1; i<=m; i++) cnt[i]=0;
for (int i=1; i<=m; i++){
for (int j=i; j<=m; j++) cnt[j]+=ted[i][j];
int t=C[i];
for (int j=i; j<=m && t; j++){
int tt=min(t, cnt[j]);
cnt[j]-=tt;
t-=tt;
}
if (t) return 0;
}
return 1;
}
int can(int mm, int CC[]){
m=mm;
for (int i=0; i<m; i++) C[i+1]=CC[i];
sort(C+1, C+m+1);
if (m>=SQ) return SolveBig();
return SolveSmall();
}
