#include <bits/stdc++.h>
struct Interval {
int l;
int r;
int pos;
};
using namespace std;
typedef long long ll;
const int N = (int) 5e5 + 7;
const int Q = (int) 2e5 + 7;
pair<int, int> a[N];
vector<int> pos[N];
int n, q;
struct Node {
Node *left;
Node *right;
int sum;
Node() {
left = NULL;
right = NULL;
sum = 0;
}
};
Node *segt[N];
void build(Node *root, int tl, int tr) {
if (tl == tr) {
root->sum = 0;
} else {
root->left = new Node();
root->right = new Node();
int tm = (tl + tr) / 2;
build(root->left, tl, tm);
build(root->right, tm + 1, tr);
root->sum = root->left->sum + root->right->sum;
}
}
void update(Node *root, Node *prev, int tl, int tr, int pos, int val) {
if (tl == tr) {
root->sum += val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
root->left = new Node();
root->right = prev->right;
update(root->left, prev->left, tl, tm, pos, val);
} else {
root->left = prev->left;
root->right = new Node();
update(root->right, prev->right, tm + 1, tr, pos, val);
}
root->sum = root->left->sum + root->right->sum;
}
}
int query(Node *root, int tl, int tr, int l, int r) {
if (l <= tl && tr <= r) {
return root->sum;
}
int tm = (tl + tr) / 2;
if (l <= tm && r <= tm) {
return query(root->left, tl, tm, l, r);
} else if (tm + 1 <= l && tm + 1 <= r) {
return query(root->right, tm + 1, tr, l, r);
} else {
return query(root->left, tl, tm, l, tm) + query(root->right, tm + 1, tr, tm + 1, r);
}
}
int getkth(int l, int r, int k) {
int low = 0, high = n, ret = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (query(segt[mid], 1, n, l, r) < k) {
ret = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ret + 1;
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; i++) {
a[i].first = A[i - 1];
a[i].second = B[i - 1];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
pos[a[i].second].push_back(i);
}
segt[0] = new Node();
build(segt[0], 1, n);
for (int i = 1; i <= n; i++) {
segt[i] = new Node();
if ((int) pos[i].size() == 0) segt[i] = segt[i - 1];
for (auto &it : pos[i]) {
update(segt[i], segt[i - 1], 1, n, it, 1);
}
}
}
int can(int M, int K[]) {
q = M;
vector<int> queries(q + 1);
for (int i = 1; i <= q; i++) {
queries[i] = K[i - 1];
}
sort(queries.begin(), queries.end());
int j = 1;
vector<Interval> st;
for (int i = 1; i <= q; i++) {
int low = 0, high = n, ret = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid].first <= queries[i]) {
ret = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
ret++;
if (j < ret) st.push_back({j, ret - 1, 0});
j = ret;
int aux = queries[i];
while (aux > 0) {
if ((int) st.size() == 1) {
st[0].pos = max(st[0].pos, query(segt[queries[i] - 1], 1, n, st[0].l, st[0].r));
if (st[0].pos + aux <= (st[0].r - st[0].l + 1)) {
st[0].pos += aux;
aux = 0;
break;
} else {
return false;
}
} else {
st[(int) st.size() - 1].pos = max(st[(int) st.size() - 1].pos, query(segt[queries[i] - 1], 1, n, st[(int) st.size() - 1].l, st[(int) st.size() - 1].r));
st[(int) st.size() - 2].pos = max(st[(int) st.size() - 2].pos, query(segt[queries[i] - 1], 1, n, st[(int) st.size() - 2].l, st[(int) st.size() - 2].r));
int kth = getkth(st[(int) st.size() - 2].l, st[(int) st.size() - 2].r, st[(int) st.size() - 2].pos);
int newadded = max(0, query(segt[kth - 1], 1, n, st[(int) st.size() - 1].l, st[(int) st.size() - 1].r) - st[(int) st.size() - 1].pos);
if (newadded <= aux) {
st[(int) st.size() - 2].pos += st[(int) st.size() - 1].pos + newadded;
st[(int) st.size() - 2].r = st[(int) st.size() - 1].r;
st.pop_back();
aux -= newadded;
} else {
st[(int) st.size() - 1].pos += aux;
aux = 0;
}
}
}
}
return true;
}
