#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second
struct node{
node* l;
node* r;
int sum;
node(int val){
l=nullptr;
r=nullptr;
sum=val;
}
node(node* lll, node* rr){
l=lll;
r=rr;
sum=l->sum + r->sum;
}
};
node* build(int l, int r){
if(l==r) return new node(0);
int m=(l+r)/2;
return new node(build(l,m), build(m+1,r));
}
node* update(node* cur, int l, int r, int tar){
if(l==r) return new node(cur->sum+1);
int m=(l+r)/2;
if(tar<=m) return new node(update(cur->l, l, m, tar), cur->r);
return new node(cur->l, update(cur->r, m+1, r, tar));
}
int query(node* cur, int l, int r, int ql){
if(ql<=l) return cur->sum;
int m=(l+r)/2, ret=0;
if(ql<=m) ret += query(cur->l, l, m, ql);
ret += query(cur->r, m+1, r, ql);
return ret;
}
int n;
v<ii> points;
v<node*> roots;
int getRect(int x1, int x2, int y){
ii p1 = {x1, -1}, p2 = {x2+1, -1};
int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
return query(roots[ind2], 1, n, y) - query(roots[ind1], 1, n, y);
}
void init(int N, int A[], int B[]) {
n=N;
for(int i=0; i<n; i++) points.push_back({A[i], B[i]});
roots.push_back(build(1,n));
sort(points.begin(), points.end());
for(ii it:points) roots.push_back(update(roots.back(), 1, n, it.se));
}
int cnt=0;
int can(int M, int K[]) {
sort(K, K+M);
if(M>400){
priority_queue<ii> pq;
int j=0;
for(int i=0; i<M; i++){
while(j<n && points[j].fi<=K[i]){
pq.push({-points[j].se, points[j].fi});
j++;
}
while(pq.size()>0 && -pq.top().fi<K[i]) pq.pop();
if(pq.size()<K[i]) return 0;
for(int k=0; k<K[i]; k++) pq.pop();
}
return 1;
}
v<int> dp(M);
for(int i=0; i<M; i++){
dp[i] = getRect(0, K[i], K[i]) - K[i];
for(int j=0; j<i; j++){
dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]);
}
if(dp[i]<0) return 0;
}
return 1;
}
