#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
int n;
vector<pii> v;
bool cmp(pii &lhs, pii &rhs) {
if (lhs.ss != rhs.ss) return lhs.ss < rhs.ss;
return lhs.ff < rhs.ff;
}
const int mxN = 1e5 + 1;
vector<int> seg[4 * mxN];
void merge(vector<int> &res, vector<int> &lhs, vector<int> &rhs) {
int lptr = 0, rptr = 0;
while (lptr < lhs.size() && rptr < rhs.size()) {
if (lhs[lptr] < rhs[rptr]) {
res.pb(lhs[lptr]); lptr++;
} else {
res.pb(rhs[rptr]); rptr++;
}
}
while (lptr < lhs.size()) {
res.pb(lhs[lptr]); lptr++;
}
while (rptr < rhs.size()) {
res.pb(rhs[rptr]); rptr++;
}
}
void build(int l = 1, int r = n, int idx = 1) {
if (l == r) {
seg[idx] = {v[l].ff};
return;
}
int mid = (l + r) >> 1;
build(l, mid, (idx << 1));
build(mid + 1, r, (idx << 1) | 1);
merge(seg[idx], seg[(idx << 1)], seg[(idx << 1) | 1]);
}
int query(int st, int tar, int nos, int l = 1, int r = n, int idx = 1) {
// cerr << "query " << st << ' ' << tar << ' ' << nos << endl;
if (l == r) {
nos -= (seg[idx][0] <= tar);
if (nos <= 0) return l;
else return -nos;
}
int mid = (l + r) >> 1;
if (st <= l) {
int cnts;
cnts = upper_bound(seg[idx].begin(), seg[idx].end(), tar) - seg[idx].begin();
if (cnts < nos) return -(nos - cnts);
cnts = upper_bound(seg[(idx << 1)].begin(), seg[(idx << 1)].end(), tar) - seg[(idx << 1)].begin();
if (cnts >= nos) return query(st, tar, nos, l, mid, (idx << 1));
else return query(st, tar, nos - cnts, mid + 1, r, (idx << 1) | 1);
} else if (st <= mid) {
int res = query(st, tar, nos, l, mid, (idx << 1));
if (res > 0) return res;
return query(st, tar, -res, mid + 1, r, (idx << 1) | 1);
} else {
return query(st, tar, nos, mid + 1, r, (idx << 1) | 1);
}
}
void init(int N, int A[], int B[]) {
n = N;
v.resize(n + 1); v[0] = {0, 0};
for (int i = 1; i <= n; i++) {
v[i] = {A[i - 1], B[i - 1]};
}
sort(v.begin() + 1, v.end(), cmp);
build();
}
int can(int M, int K[]) {
if (n == 1) return (K[0] == 1);
int m = M;
vector<int> tar(m);
for (int i = 0; i < m; i++) tar[i] = K[i];
sort(tar.begin(), tar.end());
int pos = 0;
for (int &need : tar) {
pos++;
if (pos > n) return 0;
if (v[n].ss < need) return 0;
int lb = 1, rb = n;
while (lb < rb) {
int mid = (lb + rb) >> 1;
if (v[mid].ss >= need) rb = mid;
else lb = mid + 1;
// cerr << lb << ' ' << rb << ' ' << need << ' ' << v[1].ss << endl;
}
pos = max(pos, lb);
// cerr << "lb " << lb << endl;
int res = query(pos, need, need);
// cerr << "res " << res << endl;
if (res < 0) return 0;
pos = res;
}
return 1;
}
/*
fix pos (bounded by upper bound)
range descend find kth element >= tar (bounded by lower bound)
can be maintained by merge sort tree?
*/
