#include "bits/stdc++.h"
#include "teams.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int BL = 350;
const int N = 5e5 + 5;
struct Node{
Node* lc;
Node* rc;
int sum;
Node(){
lc = rc = NULL;
sum = 0;
}
};
vector<Node*> seg;
vector<array<int,2>> v;
int n;
Node* build(int l,int r){
if(l == r) return new Node();
int m = (l + r) / 2;
Node* res = new Node();
res -> lc = build(l, m);
res -> rc = build(m + 1, r);
return res;
}
Node* upd(Node* rt,int l,int r,int ind){
if(l == r){
Node* res = new Node();
res -> sum = rt -> sum + 1;
return res;
}
Node* res = new Node();
int m = (l + r) / 2;
if(ind <= m){
res -> lc = upd(rt -> lc, l, m, ind);
res -> rc = rt -> rc;
}
else{
res -> lc = rt -> lc;
res -> rc = upd(rt -> rc, m + 1, r, ind);
}
res -> sum = res -> lc -> sum + res -> rc -> sum;
return res;
}
int query(Node* rt,int l,int r,int gl,int gr){
if(r < gl || l > gr) return 0;
if(l >= gl && r <= gr) return rt -> sum;
int m = (l + r) / 2;
return query(rt -> lc, l, m,gl,gr) + query(rt -> rc,m + 1, r, gl, gr);
}
void init(int _n, int A[], int B[]){
n = _n;
for(int i = 0 ; i < n ; i++) v.push_back({A[i], B[i]});
sort(all(v));
seg.push_back(build(1,N));
for(int i = 0 ; i < n ; i++) seg.push_back(upd(seg.back(),1,N,v[i][1]));
}
int Get_Sum(int l,int r){
int it = upper_bound(all(v),array<int,2>{l+1,-1}) - v.begin();
return query(seg[it],1,N,r,N);
}
int can(int M, int K[]){
sort(K,K+M);
if(M >= BL){
int p = 0;
priority_queue<int,vector<int>,greater<int>> pq;
for(int i = 0 ; i < M ; i++){
int val = K[i];
while(p < n && v[p][0] <= val) pq.push(v[p++][1]);
while(!pq.empty() && pq.top() < val) pq.pop();
if(sz(pq) < val) return 0;
while(val--) pq.pop();
}
return 1;
}
int dp[M];
memset(dp,0,sizeof(dp));
for(int i = 0; i < M; i++){
for(int j = i - 1 ; j >= 0 ; j--) dp[i] = min(dp[i], dp[j] - Get_Sum(K[j], K[i]));
dp[i] += Get_Sum(K[i], K[i]) - K[i];
if(dp[i] < 0) return 0;
}
return 1;
}
