#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 5e5 + 5;
struct Seg{
vi seg;
vi l, r;
inline void Add() {
seg.push_back(0), l.push_back(0), r.push_back(0);
}
Seg() {
Add();
}
inline void Fix(int i) {
if (!l[i]) {
l[i] = seg.size();
Add();
r[i] = seg.size();
Add();
}
}
int update(int i, int ind, int L, int R) {
int copy = seg.size();
Add();
seg[copy] = seg[ind];
if (L + 1 == R) {
seg[copy]++;
return copy;
}
Fix(ind);
l[copy] = l[ind], r[copy] = r[ind];
if (i < (L + R) >> 1) {
int j = update(i, l[ind], L, (L + R) >> 1);
l[copy] = j;
} else {
int j = update(i, r[ind], (L + R) >> 1, R);
r[copy] = j;
}
seg[copy] = seg[l[copy]] + seg[r[copy]];
return copy;
}
int query(int a, int b, int ind, int L, int R) {
if (a <= L && R <= b) return seg[ind];
if (R <= a || b <= L) return 0;
int x1 = l[ind] ? query(a, b, l[ind], L, (L + R) >> 1) : 0;
int x2 = r[ind] ? query(a, b, r[ind], (L + R) >> 1, R) : 0;
return x1 + x2;
}
};
int a[MAX_N], b[MAX_N], ind[MAX_N];
int n;
Seg seg;
int roots[MAX_N];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++) {
a[i] = A[i];
b[i] = B[i];
ind[i] = i;
}
sort(ind, ind + n, [&] (int i, int j) {
return (a[i] == a[j] ? b[i] < b[j] : a[i] < a[j]);
});
for (int i = 1, j = 0; i <= n; i++) {
roots[i] = roots[i - 1];
for (; j < n && a[ind[j]] <= i; j++) {
roots[i] = seg.update(b[ind[j]], roots[i], 1, n + 1);
}
}
}
int can(int m, int k[]) {
sort(k, k + m);
ll s = 0;
vii v;
for (int i = 0; i < m; i++) {
int j = i;
while (j + 1 < m && k[j + 1] == k[j]) j++;
v.push_back({k[i], (j - i + 1) * k[i]});
s += k[i] * (j - i + 1);
i = j;
}
if (s > n) return 0;
int sz = v.size();
v.push_back({n + 1, 0});
vi erased(sz);
for (int i = 0; i < sz; i++) {
auto [x, cnt] = v[i];
for (int j = i; j < sz && cnt; j++) {
int count = seg.query(v[j].x, v[j + 1].x, roots[x], 1, n + 1) - erased[j];
erased[j] += min(count, cnt);
cnt -= min(count, cnt);
}
if (cnt) return 0;
}
return 1;
}
//4
//2 4
//1 2
//2 3
//2 3
//2
//2 1 3
//2 1 1
