#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
const int N = 5e5 + 5, K = 800, INF = 1e9 + 5;
int B_SIZE, B_CNT;
int n, blockmin[N], blockmax[N];
pair<int, int> arr[N];
vector<pair<int, int>> block[N];
struct Fenwick{
int tree[K], preup = -1;
vector<pair<int, int>> hist;
int getsum(int r){
int sum = 0;
for(int i = r + 1; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
int query(int pos){
return getsum(pos) - getsum(pos - 1);
}
void update(int pos, int val, bool keephist = true){
if(keephist) hist.push_back({pos, val});
for(int i = pos + 1; i < K; i += i & -i) tree[i] += val;
}
void clearhist(){
for(int i = (int)hist.size() - 1; i >= 0; i--) update(hist[i].first, -hist[i].second, false);
hist.clear();
preup = -1;
}
};
Fenwick fw[K];
void init(int N_, int A[], int B[]){
n = N_;
B_SIZE = (int)sqrt(n) + 1, B_CNT = (n + B_SIZE - 1) / B_SIZE;
for(int i = 0; i < n; i++) arr[i] = {A[i], B[i]};
sort(arr, arr + n);
for(int i = 0; i < n; i++) block[i / B_SIZE].push_back({arr[i].second, arr[i].first});
for(int i = 0; i < B_CNT; i++){
blockmin[i] = INF, blockmax[i] = -INF;
sort(block[i].begin(), block[i].end(), greater<pair<int, int>>());
for(int j = 0; j < block[i].size(); j++){
blockmin[i] = min(blockmin[i], block[i][j].second);
blockmax[i] = max(blockmax[i], block[i][j].second);
fw[i].update(j, 1, false);
}
}
}
int can(int M, int k[]){
sort(k, k + M, greater<int>());
for(int i = 0; i < B_CNT; i++) fw[i].clearhist();
for(int cur = 0; cur < M; cur++){
int rem = k[cur], ptr = B_CNT - 1;
while(rem > 0){
if(ptr == -1) return 0;
else if(blockmin[ptr] <= k[cur]){
if(blockmax[ptr] <= k[cur]){
int l = -1, r = block[ptr].size(), m;
while(r - l > 1){
m = l + (r - l) / 2;
if(block[ptr][m].first >= k[cur]) l = m;
else r = m;
}
int cnt = max(fw[ptr].getsum(l), 0);
if(cnt < rem){
rem -= cnt;
fw[ptr].preup = max(fw[ptr].preup, l);
fw[ptr].update(0, -cnt);
ptr--;
continue;
}
}
vector<pair<int, int>> v;
for(int j = 0; j < block[ptr].size(); j++){
if(block[ptr][j].first >= k[cur] && block[ptr][j].second <= k[cur] && fw[ptr].query(j) > 0 && j > fw[ptr].preup){
v.push_back({block[ptr][j].second, j});
}
}
sort(v.begin(), v.end(), greater<pair<int, int>>());
for(int i = 0; i < v.size(); i++){
if(rem == 0) break;
fw[ptr].update(v[i].second, -1);
rem--;
}
}
ptr--;
}
}
return 1;
}
