#include "teams.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
struct NODE{
int val;
NODE *l, *r;
NODE(int _val, NODE *_l=nullptr, NODE *_r=nullptr): val(_val), l(_l), r(_r) {}
NODE* in(int st, int fin, int k){
if(k<st||k>fin)return this;
if(st==fin)return new NODE(this->val+1, l, r);
return new NODE(this->val+1, l->in(st, (st+fin)/2, k), r->in((st+fin)/2+1, fin, k));
}
int query(int st, int fin, int ll, int rr){
if(rr<st||ll>fin)return 0;
if(ll<=st&&rr>=fin)return this->val;
return l->query(st, (st+fin)/2, ll, rr)+r->query((st+fin)/2+1, fin, ll, rr);
}
};
NODE *root[500010];
int pos[500010], n;
void init(int N, int A[], int B[]){
n=N;
vector<pii> vc;
for(int i=0; i<n; i++){
vc.pb(mp(A[i], B[i]));
}
sortvec(vc);
root[0]=new NODE(0);
root[0]->l=root[0]->r=root[0];
for(int i=1; i<=n; i++){
root[i]=root[i-1]->in(1, n, vc[i-1].S);
pos[vc[i-1].F]=i;
}
for(int i=1; i<=n; i++){
if(!pos[i])pos[i]=pos[i-1];
}
}
int can(int m, int k[]){
sort(k, k+m);
vector<int> vc, ch;
for(int i=0; i<m; i++)vc.pb(k[i]);
compress(vc);
ch.resize(vc.size());
int point=0, point2=0;
for(int i=0; i<m; i++){
while(vc[point]<k[i])point++;
if(i&&k[i]!=k[i-1])point2=point;
int temp=k[i];
while(temp&&point2<vc.size()){
int ans;
if(point2==vc.size()-1)ans=root[pos[k[i]]]->query(1, n, vc[point2], n)-ch[point2];
else ans=root[pos[k[i]]]->query(1, n, vc[point2], vc[point2+1]-1)-ch[point2];
ch[point2]+=min(ans, temp);
temp-=min(ans, temp);
if(!temp)break;
point2++;
}
if(temp)return 0;
}
return 1;
}
//thx a lot to short impl. of PST to gnoor
