#include "teams.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int MAXN = 5e5 + 12, BS = 300;
struct node{
int val = 0;
node *l = nullptr, *r = nullptr;
node(int _val = 0, node* _l = nullptr, node* _r = nullptr){
val = _val, l = _l, r = _r;
}
};
int getVal(node* v){
return v ? v->val: 0;
}
node* upd(node* v, int tl, int tr, int pos, int val){
if(tl == tr) return new node(getVal(v) + val);
int tm = (tl + tr) / 2;
if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v);
else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val));
v->val = getVal(v->l) + getVal(v->r);
return v;
}
int get(node* v, int tl, int tr, int l, int r){
if(tl > r || l > tr) return 0;
if(tl >= l && tr <= r) return getVal(v);
int tm = (tl + tr) / 2;
return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0);
}
node* root[MAXN];
int n, dp[MAXN];
vector< int > rv[MAXN], mine[MAXN];
void init(int N, int A[], int B[]) {
n = N, root[0] = new node();
for(int i = 0;i < n;i++)
rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]);
for(int i = 1;i <= n;i++){
root[i] = root[i - 1];
for(int v: rv[i]){
root[i] = upd(root[i], 1, n, v, 1);
}
}
}
int can(int M, int K[]) {
sort(K, K + M);
if(M <= BS){
for(int i = 0;i < M;i++){
dp[i] = get(root[n - K[i] + 1], 1, n, 1, K[i]) - K[i];
for(int j = 0;j < i;j++){
dp[i] = min(dp[i], dp[j] + get(root[n - K[i] + 1], 1, n, K[j] + 1, K[i]) - K[i]);
}
if(dp[i] < 0) return 0;
}
}
else{
priority_queue< int > st;
for(int i = 1, j = 0;i <= n && j < M;i++){
while(!st.empty() && -st.top() < i)
st.pop();
for(int v: mine[i])
st.push(-v);
while(K[j] == i){
if(i > st.size()) return 0;
while(K[j]--) st.pop();
j++;
}
}
}
return 1;
}
