#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "teams.h"
vector<pair<int, int> > st;
bool comp(pair<int, int> p1, pair<int, int> p2){
if(p1.second == p2.second) return (p1.first < p2.first);
else return (p1.second < p2.second);
}
void init(int N, int A[], int B[]){
for(int i = 0; i < N; i++){
st.pb({A[i], B[i]});
}
sort(st.begin(), st.end(), comp);
}
struct SEGT{
vector<int> tree;
void init(int n){
tree.assign(4*n, 0);
}
void update(int ind, int l, int r, int pos, int val){
if(l == r){
tree[ind] += val;
}
else{
int m = (l + r)/2;
if(pos <= m) update(ind*2, l, m, pos, val);
else update(ind*2+1, m+1, r, pos, val);
tree[ind] = min(tree[ind*2], tree[ind*2+1]);
}
}
int query(int ind, int l, int r, int ql, int qr){
if(l > r || ql > qr || l > qr || r < ql) return (tree.size()/4 + 1);
if(l >= ql && r <= qr){
int m = (l + r)/2;
if(l == r) return l;
else if(tree[ind*2] == 0) return query(ind*2, l, m, ql, qr);
else if(tree[ind*2+1] == 0) return query(ind*2+1, m+1, r, ql, qr);
else return (tree.size()/4 + 1);
}
else{
int m = (l + r)/2;
return min(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
}
}
};
int can(int M, int K[]) {
sort(K, K + M);
vector<int> cnt(M);
SEGT seg;
seg.init(M);
for(int i = 0; i < st.size(); i++){
auto starti = lower_bound(K, K + M, st[i].first) - K;
if(starti >= M) continue;
auto endi = upper_bound(K, K + M, st[i].second) - K;
int ind = seg.query(1, 1, M, starti + 1, endi);
if(ind > M) continue;
cnt[ind - 1]++;
if(cnt[ind - 1] == K[ind - 1]){
seg.update(1, 1, M, ind, 1);
}
/*
for(int j = starti; j < endi; j++){
if(cnt[j] < K[j]){
cnt[j]++;
break;
}
}
*/
}
bool ok = 1;
for(int i = 0; i < M; i++){
if(cnt[i] != K[i]) ok = 0;
}
return ok;
}
