#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "teams.h"
struct Node {
int cnt;
int L, R;
}tree[500005 * 42];
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);
}
int tot_S;
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;
vector<pair<int, int>> st(N);
for(int i = 0; i < N; ++i) {
st[i] = {A[i], B[i]};
}
ranges::sort(st);
int sid = 0;
for(int i = 1; i <= N; i++) {
root[i] = root[i - 1];
while(sid < N && st[sid].first == i) {
root[i] = upd(root[i], 1, N, st[sid].second);
sid++;
}
}
}
int can(int M, int K[]) {
sort(K, K + M);
vector<pair<int, int>> projects;
ll tot_need = 0;
for(int i = 0; i < M; ++i) {
tot_need += K[i];
if(projects.empty() || projects.back().first != K[i])
projects.push_back({K[i], K[i]});
else
projects.back().second += K[i];
}
if(tot_need > tot_S) return 0;
int num_p = projects.size();
vector<int> dp(num_p + 1, 0);
for(int i = 1; i < num_p + 1; ++i) {
int curk = projects[i - 1].first;
int curNeed = projects[i - 1].second;
dp[i] = cnt_st(curk, curk) - curNeed;
for(int j = 1; j < i; ++j) {
int prevk = projects[j - 1].first;
int available = cnt_st(curk, curk) - cnt_st(prevk, curk);
dp[i] = min(dp[i], dp[j] + available - curNeed);
}
if(dp[i] < 0) return 0;
}
return 1;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int n;
// cin >> n;
// int a[n], b[n];
// for (int i = 0; i < n; ++i) {
// cin >> a[i] >> b[i];
// }
// init(n, a, b);
// int q;
// cin >> q;
// for (int qq = 0; qq < q; ++qq) {
// int m;
// cin >> m;
// int k[m];
// for (int i = 0; i < m; ++i) {
// cin >> k[i];
// }
// cout << can(m, k) << "\n";
// }
// return 0;
// }
