#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define V vector
#define vi vector<int>
#define vl vector<long long>
#define vb vector<bool>
#define vs vector<string>
#define vd vector<double>
#define pi pair<int,int>
#define pd pair<double,double>
#define pl pair<long long, long long>
#define all(i) i.begin(),i.end()
#define REP(i,a,b) for(int i = a; i <= b; i++)
#define PER(i,a,b) for(int i = a; i >= b; i--)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i > b; i--)
#define indlb(v, x) (distance((v).begin(), lower_bound((v).begin(), (v).end(), (x))))
#define indub(v, x) (distance((v).begin(), upper_bound((v).begin(), (v).end(), (x))))
#define sz(i) (int) i.size()
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define currtime chrono::high_resolution_clock::now().time_since_epoch().count()
#define F first
#define S second
#define mp make_pair
template<typename T>
void printv(V<T> &x){
for(T i : x)cout << i << " ";
cout << "\n";
}
template<typename T>
void readv(V<T> &x){
for(T &y : x)cin>>y;
}
inline int nxt(){
int x; cin >> x; return x;
}
constexpr int MX_NODES = 4e6;
constexpr int RANGE_SZ = 5e5+5;
int tree[MX_NODES], l[MX_NODES], r[MX_NODES];
int timer = -1;
int build(int tl, int tr, const vector<int> &arr) {
const int cur = ++timer;
if (tl == tr) {
tree[timer] = arr[tl];
return cur;
}
int mid = (tl + tr) / 2;
l[cur] = build(tl, mid, arr);
r[cur] = build(mid+1, tr, arr);
tree[cur] = tree[l[cur]] + tree[r[cur]];
return cur;
}
int upd(int pos, int add, int v, int tl = 0, int tr = RANGE_SZ - 1) {
const int cur = ++timer;
if (tl == tr) {
tree[cur] = add + tree[v];
return cur;
}
l[cur] = l[v], r[cur] = r[v];
const int mid = tl + (tr - tl) / 2;
if (pos > mid) {
r[cur] = upd(pos, add, r[v], mid + 1, tr);
} else {
l[cur] = upd(pos, add, l[v], tl, mid);
}
tree[cur] = tree[l[cur]] + tree[r[cur]];
return cur;
}
int query(int v, int l1,int r1, int tl = 0, int tr = RANGE_SZ - 1) {
if(l1<=tl && tr<=r1) return tree[v];
const int mid = tl + (tr - tl) / 2;
int sum = 0;
if(mid>=l1) sum+= query(l[v], l1, r1, tl, mid);
if(mid<r1)sum+= query(r[v],l1,r1,mid+1,tr);
return sum;
}
int n;
vi roots;
V<pi> students;
void init(int n1, int *A, int *B){
n = n1;
students.resize(n);
roots.resize(n+1);
REP(i,0,n-1){
students[i].F=A[i];
students[i].S=B[i];
}
sort(all(students));
vi v(RANGE_SZ+1);
roots[0] = build(0, RANGE_SZ, v);
REP(i,1,n){
// cout << students[i-1].S << endl;
roots[i] = upd(students[i-1].S,1,roots[i-1]);
}
}
int can(int m, int *K){
vi k(m);
rep(i,0,m){
k[i]=K[i];
}
sort(all(k));
// printv(k);
int maxp=0;
vi big;
int sum = 0;
REP(i,0,m-1){
sum+=k[i];
// cout << i << " " << m << endl;
if(i==m-1 || k[i]!=k[i+1]){
int t = indlb(students,make_pair(k[i]+1,0));
//check if i die
// cout << i << " " << sum << " " << t << " " << maxp << " " <<query(roots[t],0,n) << endl;
if(query(roots[t],0,n)-sum<maxp)return 0;
//update minp
// cout << k[i] << " " << query(roots.back(),0,k[i]) << endl;
smax(maxp,query(roots.back(),0,k[i])-sum);
}
}
return 1;
}
