#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int SQRT = 2000;
int n;
map<int,int> fen[maxn];
void add(int x, int y){
for (int idx = x; idx < maxn; idx += idx & -idx)
for (int idy = y; idy < maxn; idy += idy & -idy)
fen[idx][idy] ++;
}
int get(int x, int y){
int ret = 0;
for (; x; x -= x & -x)
for (int idy = y; idy; idy -= idy & -idy)
ret += fen[x][idy];
return ret;
}
int get(int x, int l, int r){
return get(x, r) - get(x, l-1);
}
void init(int N, int A[], int B[]){
n = N;
for (int i = 0; i < n; i++)
add(A[i],B[i]);
}
int up[SQRT], bup[SQRT];
int can(int m, int k[]){
sort(k,k+m);
int idx = 0, cnt = 0;
for (int i = 0; i < m; i++){
cnt ++;
if (i == m-1 or k[i] != k[i+1]){
if (1LL*cnt*k[i] > n)
return false;
up[idx] = k[i], bup[idx] = cnt*k[i];
cnt = 0, idx++;
continue;
}
}
int CommonUse = 0;
up[idx] = n+1;
for (int i = 0; i < idx; i++){
int me = get(up[i], up[i], up[i+1]-1);
int LastUse = 0;
if (i > 0)
LastUse = get(up[i-1], up[i], up[i+1]-1);
LastUse = min(CommonUse, LastUse);
CommonUse -= LastUse;
me -= LastUse;
bup[i] -= me;
if (bup[i] > 0){
int T = get(up[i], up[i+1], n);
if (T < bup[i])
return false;
CommonUse += bup[i];
}
}
return true;
}
