#include "teams.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 5e5 + 5;
const int TREE_SIZE = MAX * 20;
int n;
//vector<pii> v;
int tree[TREE_SIZE], L[TREE_SIZE], R[TREE_SIZE];
int nxt = 0;
int roots[MAX];
void build(int node, int l, int r){
if(l == r) return;
int mid = (l + r) / 2;
L[node] = ++nxt;
R[node] = ++nxt;
build(L[node], l, mid);
build(R[node], mid + 1, r);
}
int update(int node, int l, int r, int pos){
int id = ++nxt;
tree[id] = tree[node] + 1;
if(l == r) return id;
L[id] = L[node];
R[id] = R[node];
int mid = (l + r) >> 1;
if(pos <= mid){
L[id] = update(L[id], l, mid, pos);
}
else{
R[id] = update(R[id], mid + 1, r, pos);
}
return id;
}
int ask(int node, int l, int r, int ql, int qr){
if(ql > r || qr < l){
return 0;
}
if(ql <= l && r <= qr){
return tree[node];
}
int mid = (l + r) >> 1;
return ask(L[node], l, mid, ql, qr) + ask(R[node], mid + 1, r, ql, qr);
}
void init(int N, int A[], int B[])
{
n = N;
vector<int> a[n + 1];
for (int i = 0; i < n; i++)
{
//v.push_back({A[i], B[i]});
a[A[i]].push_back(B[i]);
}
for (int i = 1; i <= n; i++)
{
roots[i] = roots[i - 1];
for(int r:a[i]){
roots[i] = update(roots[i], 1, MAX, r);
}
}
}
int can(int M, int K[])
{
sort(K, K + M);
int s = 0;
vector<pii> v;
for (int i = 0; i < M; i++)
{
if(!v.empty() && v[v.size() - 1].first == K[i]){
v[v.size() - 1].second += K[i];
}
else{
v.push_back({K[i], K[i]});
}
s += K[i];
}
if(s > n) return false;
vector<pii> blocks;
for (int i = 0; i < v.size(); i++)
{
if(!blocks.empty()){
blocks[blocks.size() - 1].second = v[i].first - 1;
}
blocks.push_back({v[i].first, 0});
}
blocks[blocks.size() - 1].second = n;
vector<int> used;
used.resize(blocks.size(), 0);
for (int i = 0; i < v.size(); i++)
{
int need = v[i].second;
for (int j = i; j < blocks.size(); j++)
{
int c = min(ask(roots[v[i].first], 1, MAX, blocks[j].first, blocks[j].second) - used[j], need);
used[j] += c;
need -= c;
if(need == 0) break;
}
if(need != 0) return false;
}
return true;
}
