#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++;
}
}
}
struct Project {
int k, need;
};
struct State {
int id, L, R;
};
vector<Project> projects;
int dp[500005];
ll g(int j, int x) {
if(!j) return cnt_st(0, x);
return (ll)dp[j] - cnt_st(projects[j - 1].k, x);
}
int can(int M, int K[]) {
sort(K, K + M);
projects.clear();
ll tot_need = 0;
for(int i = 0; i < M; ++i) {
tot_need += K[i];
if(projects.empty() || projects.back().k != K[i])
projects.push_back({K[i], K[i]});
else
projects.back().need += K[i];
}
if(tot_need > tot_S) return 0;
int num_p = projects.size();
vector<State> stk;
stk.push_back({0, 1, tot_S});
for(int i = 1; i < num_p + 1; ++i) {
int curk = projects[i - 1].k;
int curNeed = projects[i - 1].need;
while(stk.size() && stk.back().R < curk) stk.pop_back();
if(stk.empty()) return 0;
dp[i] = cnt_st(curk, curk) - curNeed + g(stk.back().id, curk);
if(dp[i] < 0) return 0;
int nxt_l = curk + 1;
int last_split = curk;
if(nxt_l > tot_S) continue;
while(stk.size()) {
State &top = stk.back();
if(g(i, top.R) <= g(top.id, top.R)) {
last_split = top.R;
stk.pop_back();
}
else {
if(g(i, top.L) <= g(top.id, top.L)) {
int l = top.L, r = top.R, split = top.L;
while(l <= r) {
int m = l + (r - l) / 2;
if(g(i, m) <= g(top.id, m)) { split = m; l = m + 1;}
else r = m - 1;
}
last_split = split;
top.L = split + 1;
}
break;
}
}
if(last_split >= curk + 1)
stk.push_back({i, curk + 1, last_split});
}
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;
// }
