#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 = 3e7;
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>r1)return 0;
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;
}
bool cmp(const vi &a, const vi &b){
if(a[1]!=b[1])return a[1]<b[1];
return a[0]<b[0];
}
int n;
vi roots;
V<vi> students;
vi students2;
vi students3;
void init(int n1, int *A, int *B){
n = n1;
students = V<vi>(n,vi(3));
roots.resize(n+1);
REP(i,0,n-1){
students[i][0]=A[i];
students[i][1]=B[i];
}
sort(all(students),cmp);
REP(i,0,n-1)students3.pb(students[i][1]);
REP(i,0,n-1)students[i][2]=i;
sort(all(students));
REP(i,0,n-1)students2.pb(students[i][0]);
vi v(RANGE_SZ+1);
roots[0] = build(0, RANGE_SZ, v);
REP(i,1,n){
roots[i] = upd(students[i-1][2],1,roots[i-1]);
}
}
int walk(int k, int u, int v, int tl = 0, int tr = RANGE_SZ-1){
if(tl==tr) return tl;
int mid = tl+(tr-tl)/2;
int nxt = tree[l[v]]-tree[l[u]];
if(nxt>=k){
return walk(k,l[u],l[v],tl,mid);
}
return walk(k-nxt,r[u],r[v],mid+1,tr);
}
int can(int m, int *K){
map<int,int> counts;
rep(i,0,m){
counts[K[i]]+=K[i];
}
V<vi> blocks;
blocks.reserve(m+2);
blocks.pb({-1,n,n});
blocks.pb({0,0,n});
for(auto p : counts){
int k = p.F;
int t = indlb(students2,k+1);
int count = p.S;
while(count){
if(sz(blocks)==0)return 0;
int x = blocks.back()[0];
int y1 = blocks.back()[1];
int y2 = blocks.back()[2];
int miny = indlb(students3,k);
smax(y1,miny);
smax(y2,miny);
blocks.pop_back();
int t2 = indlb(students2,x);
int a = query(roots[t],y1,y2-1)-query(roots[t2],y1,y2-1);
if(a<=count){
count-=a;
}
else{
int target = count+query(roots[t],0,y1-1)-query(roots[t2],0,y1-1);
int y3 = walk(target,roots[t2],roots[t])+1;
blocks.pb({x,y3,blocks.back()[1]});
break;
}
}
blocks.pb({k+1,0,blocks.back()[1]});
}
return 1;
}
