#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
struct Node{
int l, r, s;
Node *L, *R;
Node(int _l, int _r, int _s, Node *_L, Node *_R){
l = _l; r = _r; s = _s; L = _L; R = _R;
}
int query(int le, int ri){
if(le > r || ri < l) return 0;
if(le <= l && r <= ri) return s;
return L -> query(le, ri) + R -> query(le, ri);
}
Node* update(int x){
if(l > x || r < x) return this;
if(l == r) return new Node(l, r, s + 1, L, R);
return new Node(l, r, s + 1, L -> update(x), R -> update(x));
}
void build(){
if(l == r) return;
int m = (l + r) >> 1;
L = new Node(l, m, 0, NULL, NULL);
R = new Node(m + 1, r, 0, NULL, NULL);
L -> build();
R -> build();
}
};
vector<int> lol[500005];
Node* tree[500005];
int query(int x1, int y1, int x2, int y2){
--y1;
return tree[y2] -> query(x1, x2) - tree[y1] -> query(x1, x2);
}
void init(int N, int A[], int B[]) {
for(int i = 0; i < N; ++i)
lol[B[i]].push_back(A[i]);
tree[0] = new Node(1, N, 0, NULL, NULL);
tree[0] -> build();
for(int i = 1; i <= 500004; ++i){
tree[i] = tree[i - 1];
for(auto& x : lol[i]){
tree[i] = tree[i] -> update(x);
}
}
}
int le[500005];
vector<pair<int, int> > idk;
vector<int> val;
int can(int M, int K[]) {
sort(K + 0, K + M);
val.resize(M + 1);
for(int i = 0; i < M; ++i)
val[i] = le[i] = K[i];
val[M] = 500005;
idk = {{1, M}};
for(int i = 0; i < M; ++i){
int br = i;
int s;
while(idk.back().ss <= i) idk.pop_back();
while((s = query(idk.back().ff, val[br], val[i], val[idk.back().ss] - 1)) < le[i]){
le[i] -= s;
br = idk.back().ss;
idk.pop_back();
if(idk.empty()) return 0;
}
for(int j = 20; j >= 0; --j){
if(br + (1 << j) <= idk.back().ss && (s = query(idk.back().ff, val[br], val[i], val[br + (1 << j)] - 1)) >= le[i]){
le[i] -= s;
br += 1 << j;
}
}
le[br + 1] += le[i];
while(!idk.empty() && idk.back().ss <= br)
idk.pop_back();
idk.push_back({val[i] + 1, br});
}
return 1;
}
