#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
const int MAXN = 5e3+10; // ONLY FOR LOCAL
struct Node {
int val;
Node *l, *r;
Node(int x) : val(x), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) {
l = ll, r = rr;
val = 0;
if(l) val += l->val;
if(r) val += r->val;
}
Node(Node *cp) : val(cp->val), l(cp->l), r(cp->r) {}
};
pii a[MAXN];
vector<int> ri[MAXN], li[MAXN];
int n;
Node *pseg[MAXN];
bool tag = 1;
Node *build(int l=1, int r=n) {
if(l==r) return new Node(0);
int mid = (l+r)/2;
return new Node(build(l, mid), build(mid+1,r));
}
Node *update(Node *i, int ti, int x, int l=1, int r=n) {
if(l==r) return new Node(x+i->val);
int mid = (l+r)/2;
if(ti <= mid) return new Node(update(i->l, ti, x, l, mid), i->r);
else return new Node(i->l,update(i->r, ti, x, mid +1, r));
}
int find(Node *i, int tl, int k, int l = 1, int r = n) {
if(l==r) return l;
int mid =(l+r)/2;
int s = i->l->val;
if(s>=k) return find(i->l,tl,k,l,mid);
else return find(i->r,tl,k,mid+1,r);
}
int query(Node *i, int tl, int k, int l = 1, int r = n) {
if(tl>r) return 0;
if(tl<=l) {
if(tag && i->val >= k ) {
tag=0;
return find(i,tl,k,l,r);
}
else return 0;
}
int mid = (l+r)/2;
return query(i->l,tl,k,l,mid) + query(i->r,tl,k,mid+1,r);
}
struct BIT {
int bit[MAXN];
void update(int i, int x) {
for(; i <= n; i+=(i&-i)) bit[i]+=x;
}
int query(int i) {
int ans = 0;
for(; i > 0; i-=(i&-i)) ans+=bit[i];
return ans;
}
int sum(int l, int r) {
return query(r)-query(l-1);
}
} bit;
void init(int N, int A[], int B[]) {
n = N;
rep(i,0,N-1) ri[A[i]].pb(B[i]), li[B[i]].pb(A[i]);
pseg[1] = build();
rep(i,1,n) {
if(i>1) pseg[i] = new Node(pseg[i-1]);
for(int &x : ri[i]) pseg[i] = update(pseg[i], x,1);
}
}
int can(int M, int K[]) {
vector<pii> op;
sort(K, K+M);
bool ok = 1;
rep(i,0,M-1) {
int x = K[i], cnt = x;
while (cnt > 0) {
tag=1;
int kth = bit.query(x)+1;
int j = query(pseg[x],x,kth);
if (j==0) {
ok=0;
i=M;
break;
}
op.pb({li[j].back(),j});
bit.update(li[j].back(), 1);
bit.update(j+1, -1);
li[j].pop_back();
cnt--;
}
}
for(auto &[L,R] : op) {
bit.update(L,-1), bit.update(R+1,1), li[R].pb(L);
}
return ok;
}
