#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<"="<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define all(x) x.begin(), x.end()
#define pb push_back
const int MAXN=500010, SEGSZ=20000010;
int n, x, y;
int A[MAXN], B[MAXN], root[MAXN];
int seg[SEGSZ], L[SEGSZ], R[SEGSZ], ts;
priority_queue<int, vector<int>, greater<int>> pq;
int Add(int id, int tl, int tr, int pos, int val=1){
if (pos<tl || tr<=pos) return id;
int res=++ts;
if (tr-tl==1){
seg[res]=seg[id]+val;
return res;
}
int mid=(tl+tr)>>1;
L[res]=Add(L[id], tl, mid, pos, val);
R[res]=Add(R[id], mid, tr, pos, val);
seg[res]=seg[L[res]]+seg[R[res]];
return res;
}
int Get(int idl, int idr, int tl, int tr, int l, int r){
if (r<=tl || tr<=l) return 0;
if (l<=tl && tr<=r) return seg[idr]-seg[idl];
int mid=(tl+tr)>>1;
return Get(L[idl], L[idr], tl, mid, l, r) + Get(R[idl], R[idr], mid, tr, l, r);
}
void init(int nn, int AA[], int BB[]){
n=nn;
vector<pii> vec;
for (int i=0; i<n; i++) vec.pb({AA[i], BB[i]});
sort(all(vec));
for (int i=0; i<n; i++) A[i+1]=vec[i].first, B[i+1]=vec[i].second;
int j=1;
for (int i=1; i<=n; i++){
root[i]=root[i-1];
while (A[j]==i) root[i]=Add(root[i], 1, n+1, B[j++]);
}
}
pii BS(int id1, int id2, int tl, int tr, int l, int r, int val){
// cerr<<"BS "<<tl<<" "<<tr<<" "<<l<<" "<<r<<" "<<val<<"\n";
if (r<=tl || tr<=l) return {tr, 0};
if (l<=tl && tr<=r && seg[id1]-seg[id2]<val) return {tr, seg[id1]-seg[id2]};
if (tr-tl==1) return {tl, 0};
int mid=(tl+tr)>>1;
pii res=BS(L[id1], L[id2], tl, mid, l, r, val);
if (res.first<mid) return res;
pii p=BS(R[id1], R[id2], mid, tr, l, r, val-res.second);
return {p.first, p.second+res.second};
}
int Copy(int id1, int id2, int tl, int tr, int l, int r){ // set seg[id1][l...r-1] = seg[id2][l...r-1]
if (r<=tl || tr<=l) return id1;
if (l<=tl && tr<=r) return id2;
int res=++ts, mid=(tl+tr)>>1;
L[res]=Copy(L[id1], L[id2], tl, mid, l, r);
R[res]=Copy(R[id1], R[id2], mid, tr, l, r);
seg[res]=seg[L[res]]+seg[R[res]];
return res;
}
int can(int m, int C[]){
sort(C, C+m);
int used=0;
for (int i=0; i<m; i++){
int k=C[i];
pii p=BS(root[k], used, 1, n+1, k, n+1, k);
// debugp(p)
if (p.first==n+1) return 0;
used=Copy(used, root[k], 1, n+1, 1, p.first);
used=Add(used, 1, n+1, p.first, k-p.second);
}
return 1;
}
