#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax = 5e5 + 100;
struct node{
int l,r;
ll sum;
node(){
l = r = -1;
sum = 0;
}
}seg[22*nax];
ll head[nax];
int T;
void update(int n,int s,int e,int at,int val,int old){
if(s == e){
// cerr << n << ' ' << old << ' ' << seg[old].sum << '\n';
seg[n].sum += seg[old].sum + val;
return;
}
if((s+e)/2 < at)seg[n].l = seg[old].l;
else{
seg[n].l = ++T;
update(seg[n].l,s,(s+e)/2,at,val,seg[old].l);
}
if((s+e)/2+1 > at)seg[n].r = seg[old].r;
else{
seg[n].r = ++T;
update(seg[n].r,(s+e)/2+1,e,at,val,seg[old].r);
}
seg[n].sum = seg[ seg[n].l ].sum + seg[ seg[n].r ].sum;
// cerr << seg[n].sum << ' ' << s << ' ' << e << '\n';
}
ll get(int n,int s,int e,int l,int r){
if(n <= 0)return 0;
// assert(n >0);
if(s > r || e < l || l > r)return 0;
if(s >= l && e <= r)return seg[n].sum;
return get( seg[n].l , s , (s+e)/2 , l , r ) + get( seg[n].r , (s+e)/2+1 , e , l , r);
}
// int main(){
// int cur = 1;
// head[cur] = ++T;
// build(head[1],1,n);
// for(int i=0;i<q;i++){
// int t,k;
// cin>>t>>k;
// if(t == 1){//update
// int at,val;
// cin>>at>>val;
// int old = head[k];
// head[k] = ++T;
// update(head[k],1,n,at,val,old);
// }else if(t == 2){//sum
// int l,r;
// cin>>l>>r;
// cout << get(head[k],1,n,l,r) << endl;
// }else if(t == 3){//make new
// cur++;
// head[cur] = head[k];
// }
// }
// }
vector<pair<int,int>> s;
int n;
void init(int N, int A[], int B[]) {
n = N;
for(int i=0;i<n;i++)s.push_back({A[i], B[i]});
sort(all(s));
head[0] = ++T;
int lst = T;
for(int i=0;i<n;i++){
head[s[i].first] = ++T;
update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
// cerr << ' ' << head[s[i].first] << ' ' << lst << ' ' << get(head[s[i].first],1,n,1,n) << '\n';
lst = head[s[i].first];
}
for(int i=1;i<=n;i++){
if(head[i] == 0)
head[i] = head[i-1];
}
}
int can(int M, int K[]) {
// return 0;
sort(K,K+M);
int ex = 0;
int lst = 0;
multiset<pair<int,int>> k;
int id = 0;
for(int i=0;i<M;i++){
while(k.size() && k.begin()->first < K[i]){
ex -= k.begin()->second;
k.erase(k.begin());
}
// cerr << K[i] << ' ' << ex << ' ' << get(head[K[i]],1,n,K[i] , n) << '\n';
ex += K[i];
if(get(head[K[i]],1,n,K[i] , n) < ex){
return 0;
}
int lo=K[i],hi = n,to=n + 1;
while(lo <= hi){
int md = (lo + hi)/2;
if(get(head[K[i]] , 1 , n , K[i] , md) >= ex){
hi = md-1;
to = md;
}else{
lo = md + 1;
}
}
// cerr << ' ' << to << ' ' << K[i] << '\n';
int v = get(head[K[i]] , 1 , n , K[i] , to - 1);
int give = K[i] - v;
k.insert({to , give});
k.insert({to - 1 , K[i] - give});
// if(k[id] != K[i])return 0;
}
return 1;
}
