#include "teams.h"
#include "bits/stdc++.h"
using namespace std;
int n;
vector<pair<int,int>> intervals;
const int maxN = (int)5e5 + 1;
class SegmentTree{
public:
pair<int,int> Seg[maxN * 3]; //{min A value in B range, its position}
multiset<int>Left[maxN * 3];
void init(){
for (int i = 0; i < n * 3; i++){
Seg[i] = {(int)1e9, -1};
}
}
void upd(int pos, int val, int l = 1, int r = n, int k = 1){
if (l == r){
Left[k].insert(val);
Seg[k] = {*Left[k].begin(), l};
return;
}
int md = (l + r) / 2;
if (pos <= md)upd(pos,val,l,md,k*2);
else upd(pos,val,md+1,r,k*2+1);
if (Seg[k * 2].first < Seg[k * 2 + 1].first){
Seg[k] = Seg[k * 2];
}else{
Seg[k] = Seg[k * 2 + 1];
}
}
pair<int,int>query(int a, int b, int l = 1, int r = n, int k = 1){
if (l > b || r < a)return {(int)1e9,-1};
if (l >= a && r <= b){
return Seg[k];
}
auto left = query(a,b,l,(l+r)/2,k*2);
auto right = query(a,b,(l+r)/2+1,r,k*2+1);
if (left.first < right.first)return left;
else return right;
}
void remove(int pos, int val, int l = 1, int r = n, int k = 1){
if (l == r){
Left[k].erase(Left[k].find(val));
if (Left[k].size()){
Seg[k] = {*Left[k].begin(),l};
}else{
Seg[k] = {(int)1e9, -1};
}
return;
}
int md = (l + r) / 2;
if (pos <= md)remove(pos,val,l,md,k*2);
else remove(pos,val,md+1,r,k*2+1);
if (Seg[k * 2].first < Seg[k * 2 + 1].first){
Seg[k] = Seg[k * 2];
}else{
Seg[k] = Seg[k * 2 + 1];
}
}
};
SegmentTree st;
void init(int N, int A[], int B[])
{
n = N;
intervals.resize(N);
st.init();
for (int i = 0; i < N; ++i){
intervals[i] = {A[i], B[i]};
st.upd(B[i], A[i]);
}
}
int can(int M, int K[])
{
sort(K, K + M);
for (int i = 0; i < M; i++){
int l = K[i], r = n;
pair<int,int>ans = {(int)1e9, -1};
while(l<=r){
int md = (l + r) / 2;
auto response = st.query(K[i], md);
if (response.first <= K[i]){
ans = response;
r = md - 1;
}else{
l = md + 1;
}
}
if (ans.first == (int)1e9){
return 0;
}
st.remove(ans.second,ans.first);
}
return 1;
}
/*int main(){
int N, M;
cin >> N >> M;
int A[N], B[N];
for (int i = 0; i < N; i++){
cin >> A[i] >> B[i];
}
init(N,A,B);
int K[M];
for(int i = 0; i < M; i++){
cin >> K[i];
}
cout<<(can(M,K) ? "YES":"NO");
}*/
