#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct Node{
vector<int> data;
void merge(const Node &tl, const Node &tr){
data.resize(tl.data.size()+tr.data.size());
std::merge(tl.data.begin(), tl.data.end(), tr.data.begin(), tr.data.end(), data.begin());
}
};
struct SegmentTree{
int n;
vector<Node> t;
void init(int _n){
n=_n;
t.assign(4*n+1, Node());
}
void build(int k, int l, int r, pair<int, int> a[]){
if (l==r){
t[k].data.push_back(a[l].first);
return;
}
int mid=(l+r)>>1;
build(k<<1, l, mid, a);
build(k<<1|1, mid+1, r, a);
t[k].merge(t[k<<1], t[k<<1|1]);
}
int cnt;
int count(int k, int val){
return upper_bound(t[k].data.begin(), t[k].data.end(), val)-t[k].data.begin();
}
int walk(int k, int l, int r, int L, int R, int val){
if (r<L || R<l) return 0;
if (L<=l && r<=R){
int cc=count(k, val);
if (cc<cnt){
cnt-=cc;
return 0;
}
}
if (l==r) return t[k].data[0]<=val && cnt==1;
int mid=(l+r)>>1;
int ans=walk(k<<1, l, mid, L, R, val);
if (ans) return ans;
return walk(k<<1|1, mid+1, r, L, R, val);
}
} st;
const int N=5e5+10;
int n, pos[N];
pair<int, int> a[N];
void init(int _N, int _A[], int _B[]) {
n=_N;
for (int i=1; i<=n; ++i) a[i]={_A[i-1], _B[i-1]};
sort(a+1, a+n+1);
// sort(a+1, a+n+1, [&](pair<int, int> x, pair<int, int> y){
// if (x.second!=y.second) return x.second<y.second;
// return x.first<y.first;
// });
// st.init(n);
// st.build(1, 1, n, a);
// for (int i=1; i<=n; ++i) pos[i]=n+1;
// for (int i=1; i<=n; ++i) pos[a[i].second]=min(pos[a[i].second], i);
// for (int i=1; i<n; ++i) pos[i]=min(pos[i], pos[i+1]);
}
int can(int M, int K[]) {
sort(K, K+M);
multiset<int> st;
for (int i=0, j=1; i<M; ++i){
while (j<=n && a[j].first<=K[i]){
st.insert(a[j].second);
++j;
}
int cnt=K[i];
while (st.size()){
int tmp=*st.begin();
st.erase(st.begin());
if (tmp>=K[i]){
--cnt;
if (cnt==0) break;
}
}
if (cnt) return 0;
}
// for (int i=1, j=0, cnt=K[0]; i<=n; ++i){
// if (a[i].first<=K[j] && K[j]<=a[i].second){
// --cnt;
// if (!cnt){
// ++j;
// if (j==M) return 1;
// cnt=K[j];
// }
// }
// }
// int cur=1;
// for (int i=0; i<M; ++i){
// int k=K[i];
// if (pos[k]==n+1) return 0;
// cur=max(cur, pos[k]);
// st.cnt=k;
// int id=st.walk(1, 1, n, cur, n, k);
// if (!id) return 0;
// cur=id+1;
// }
return 1;
}
