#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "teams.h"
struct Node {
int cnt;
int L, R;
}tree[500005 * 40];
int root[500005];
int node_cnt;
int upd(int prev_node, int l, int r, int val) {
int curr = ++node_cnt;
tree[curr] = tree[prev_node];
tree[curr].cnt++;
if(l == r) return curr;
int m = l + r >> 1;
if(val <= m)
tree[curr].L = upd(tree[prev_node].L, l, m, val);
else
tree[curr].R = upd(tree[prev_node].R, m + 1, r, val);
return curr;
}
int qry(int node_l, int node_r, int l, int r, int ql, int qr) {
if(ql > r || qr < l || node_r == node_l) return 0;
if(ql <= l && r <= qr) return tree[node_r].cnt - tree[node_l].cnt;
int m = l + r >> 1;
return qry(tree[node_l].L, tree[node_r].L, l, m, ql, qr) +
qry(tree[node_l].R, tree[node_r].R, m + 1, r, ql, qr);
}
struct S {
int A, B;
bool operator<(const S &other) const {
return A < other.A;
}
};
int tot_S;
vector<S> st;
int cnt_st(int mxA, int mnB) {
if(mxA < 1 || mnB > tot_S) return 0;
return qry(root[0], root[mxA], 1, tot_S, mnB, tot_S);
}
void init(int N, int A[], int B[]) {
tot_S = N;
st.resize(N);
for(int i = 0; i < N; i++) {
st[i] = {A[i], B[i]};
}
sort(st.begin(), st.end());
int sid = 0;
for(int i = 1; i <= N; i++) {
root[i] = root[i - 1];
while(sid < N && st[sid].A == i) {
root[i] = upd(root[i], 1, N, st[sid].B);
sid++;
}
}
}
struct State {
int k_val, j, dp_val;
};
int can(int M, int K[]) {
ll sum = accumulate(K, K + M, 0LL);
if(sum > tot_S)
return 0;
sort(K, K + M);
vector<State> stack;
stack.push_back({0, 0, 1});
for(int i = 0; i < M; ++i) {
int curr = K[i];
while(stack.size() > 1) {
State top = stack.back();
State prev = stack.end()[-2];
int val_top = top.dp_val + cnt_st(curr, curr) - cnt_st(top.k_val, curr);
int val_prev = prev.dp_val + cnt_st(curr, curr) - cnt_st(prev.k_val, curr);
if(val_top >= val_prev) break;
stack.pop_back();
}
State best = stack.back();
int curr_dp = best.dp_val + cnt_st(curr, curr) - cnt_st(best.k_val, curr) - curr;
if(curr_dp < 0) return 0;
while(stack.size()) {
State top = stack.back();
int l = curr, r = tot_S, inter = tot_S + 1;
while(l <= r) {
int m = l + r >> 1;
int v = curr_dp + cnt_st(m, m) - cnt_st(curr, m);
int vold = top.dp_val + cnt_st(m, m) - cnt_st(top.k_val, m);
if(v <= vold) {
inter = m;
r = m - 1;
}
else l = m + 1;
}
if(inter <= curr) stack.pop_back();
else {
stack.push_back({curr, inter, curr_dp});
break;
}
}
if(stack.empty()) stack.push_back({curr, 0, curr_dp});
}
return 1;
}
