#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int val, lhs, rhs;
};
const int maxn = 500005, maxN = 3.8e7 + 5;
int n;
vector<int> rr[maxn];
int cnter = 1;
node seg[maxN];
int startnode = 1;
void build(int id, int l, int r) {
seg[id] = {0, -1, -1};
if (l == r) return;
int mid = (l+r)/2;
seg[id].lhs = ++cnter;
build(cnter, l, mid);
seg[id].rhs = ++cnter;
build(cnter, mid+1, r);
}
int update(int id, int l, int r, int target) {
if (r < target || target < l) return id;
seg[++cnter] = seg[id];
id = cnter;
if (l == r) {
seg[id].val++;
return id;
}
int mid = (l+r)/2;
seg[id].lhs = update(seg[id].lhs, l, mid, target);
seg[id].rhs = update(seg[id].rhs, mid+1, r, target);
seg[id].val = seg[seg[id].lhs].val + seg[seg[id].rhs].val;
return id;
}
int sum(int id, int l, int r, int findl, int findr) {
if (r < findl || findr < l) return 0;
if (findl <= l && r <= findr) return seg[id].val;
int mid = (l+r)/2;
return sum(seg[id].lhs, l, mid, findl, findr) + sum(seg[id].rhs, mid+1, r, findl, findr);
}
const int smol = 4000;
int psum[smol+5][smol+5];
int strt[maxn];
int qry(int t, int l, int r) {
if (r <= smol) return psum[t][r] - psum[t][l-1];
return sum(strt[t], 1, n, l, r);
}
void init(int N, int A[], int B[]) {
n = N, cnter = 1;
for (int i=1;i<=n;i++) rr[i].clear();
for (int i=0;i<n;i++) rr[A[i]].push_back(B[i]);
build(1, 1, n);
for (int i=1;i<=n;i++) {
for (int j:rr[i]) startnode = update(startnode, 1, n, j);
strt[i] = startnode;
}
int a[smol+5];
for (int i=1;i<=smol;i++) a[i] = 0;
for (int i=1;i<=n && i<=smol;i++) {
for (int j:rr[i]) if (j <= smol) a[j]++;
psum[i][0] = 0;
for (int j=1;j<=n && j<=smol;j++) psum[i][j] = psum[i][j-1] + a[j];
}
}
int can(int m, int A[]) {
sort(A, A+m);
int S = 0;
vector<pair<int,int>> vec;
for (int i=0;i<m;i++) {
if (i == 0 || A[i] != A[i-1]) vec.push_back({A[i], A[i]});
else vec.back().second += A[i];
S += A[i];
}
if (S > n) return 0;
int sz = vec.size();
vec.push_back({n+1, 0}); // not in sz
int diff[sz];
for (int i=0;i<sz;i++) diff[i] = 0;
for (int i=0;i<sz;i++) {
int taken = 0;
for (int j=i;j<sz;j++) {
int cur = qry(vec[i].first, vec[j].first, vec[j+1].first-1);
cur += diff[j];
cur = min(vec[i].second - taken, cur);
diff[j] -= cur;
taken += cur;
}
// cout << i << " " << vec[i].first << " " << vec[i].second << endl;
// for (int j=0;j<sz;j++) cout << diff[j] << " "; cout << endl;
if (taken < vec[i].second) return 0;
}
return 1;
}
