#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// --- Persistent Segment Tree Settings ---
const int MAXN = 500005;
const int MAX_NODES = MAXN * 25; // Sufficient buffer for N log N updates
struct Node {
int l, r;
int sum;
} tree[MAX_NODES];
int roots[MAXN]; // Roots for PST versions: roots[i] stores state for students with A <= i
int node_cnt = 0;
int N_global;
// --- PST Functions ---
int build(int tl, int tr) {
int id = ++node_cnt;
tree[id].sum = 0;
tree[id].l = 0;
tree[id].r = 0;
if (tl != tr) {
int tm = (tl + tr) / 2;
tree[id].l = build(tl, tm);
tree[id].r = build(tm + 1, tr);
}
return id;
}
// Update: increment count at position 'pos' (which corresponds to a B-value)
int update(int prev_node, int tl, int tr, int pos) {
int id = ++node_cnt;
tree[id] = tree[prev_node]; // Copy previous node
tree[id].sum++;
if (tl == tr) return id;
int tm = (tl + tr) / 2;
if (pos <= tm)
tree[id].l = update(tree[prev_node].l, tl, tm, pos);
else
tree[id].r = update(tree[prev_node].r, tm + 1, tr, pos);
return id;
}
// Query: count number of students with B-value in [ql, qr]
int query(int node, int tl, int tr, int ql, int qr) {
if (ql > qr) return 0;
if (ql == tl && qr == tr) return tree[node].sum;
int tm = (tl + tr) / 2;
if (qr <= tm) return query(tree[node].l, tl, tm, ql, qr);
if (ql > tm) return query(tree[node].r, tm + 1, tr, ql, qr);
return query(tree[node].l, tl, tm, ql, tm) +
query(tree[node].r, tm + 1, tr, tm + 1, qr);
}
// Helper: Count students with A <= a_lim AND B >= b_lim
int count_students(int a_lim, int b_lim) {
if (b_lim > N_global) return 0;
return query(roots[a_lim], 1, N_global, b_lim, N_global);
}
// --- Main Interface Functions ---
void init(int N, int A[], int B[]) {
N_global = N;
node_cnt = 0;
// 1. Group students by their minimum team size A[i]
// using vector of vectors to handle duplicate A values easily
vector<vector<int>> by_A(N + 1);
for (int i = 0; i < N; i++) {
by_A[A[i]].push_back(B[i]);
}
// 2. Build Persistent Segment Tree
// roots[i] represents the state including all students with A <= i
roots[0] = build(1, N);
for (int i = 1; i <= N; i++) {
roots[i] = roots[i-1];
for (int b_val : by_A[i]) {
roots[i] = update(roots[i], 1, N, b_val);
}
}
}
struct StackItem {
int idx; // Index of the group in the sorted K array
int limit_y; // The B-value limit where this strategy stops being optimal
};
int can(int M, int K[]) {
// 1. Prepare and Sort K
// We use 1-based indexing for logic, k_sorted[0] is a dummy 0.
vector<int> k_sorted(M + 1);
k_sorted[0] = 0;
for (int i = 0; i < M; i++) k_sorted[i+1] = K[i];
sort(k_sorted.begin() + 1, k_sorted.end());
// dp[i] stores the minimum "slack" (surplus capacity) after satisfying groups 1..i
vector<long long> dp(M + 1);
dp[0] = 0;
// Stack for Convex Hull / Envelope
// Stores indices j that form the lower envelope of cost functions.
// 'Newer' items (higher j) are better for small Y (team sizes).
// 'Older' items are better for large Y.
vector<StackItem> st;
st.push_back({0, N_global + 1}); // Base case: Group 0 valid for all sizes initially
for (int i = 1; i <= M; i++) {
int k_curr = k_sorted[i];
// 2. Query Phase: Determine optimal previous state 'j'
// Pop elements from the stack that are no longer optimal for the current team size k_curr.
// We need the strategy whose range COVERS k_curr.
// Stack item is valid for range [..., limit_y).
// If limit_y <= k_curr, the validity range has ended.
while (st.size() > 1 && st.back().limit_y <= k_curr) {
st.pop_back();
}
int j = st.back().idx;
// 3. Calculate DP
// Recurrence: dp[i] = dp[j] + count(K[j] < A <= K[i], B >= K[i]) - K[i]
int cnt_i = count_students(k_curr, k_curr);
int cnt_j = count_students(k_sorted[j], k_curr);
dp[i] = dp[j] + (cnt_i - cnt_j) - k_curr;
// If slack is negative, it's impossible to satisfy demands
if (dp[i] < 0) return 0;
// 4. Update Phase: Add 'i' to the stack
// We need to find the split point 'ans' such that:
// For y < ans, 'i' is better. For y >= ans, 'st.back()' (Old) is better.
// Condition for Old Better: dp[i] - count(K[i], y) >= dp[old] - count(K[old], y)
// -> count(K[i], y) - count(K[old], y) <= dp[i] - dp[old]
while (true) {
int old_idx = st.back().idx;
long long diff_dp = dp[i] - dp[old_idx];
// Binary search for the first point where Old becomes better (or equal)
int low = k_curr + 1;
int high = N_global + 1;
int ans = N_global + 1; // Default: Old is never better
while (low <= high) {
int mid = (low + high) / 2;
int count_diff = count_students(k_curr, mid) - count_students(k_sorted[old_idx], mid);
if (count_diff <= diff_dp) {
ans = mid;
high = mid - 1; // Try to find an earlier split point
} else {
low = mid + 1;
}
}
// If the calculated split point 'ans' is beyond or equal to the limit of the current Old,
// then Old is completely overshadowed by New (or Old's validity interval is empty).
// We pop Old and try comparing 'i' against the next element in stack.
if (ans >= st.back().limit_y) {
st.pop_back();
if (st.empty()) {
// This case handles when 'i' beats the base case (should essentially never happen
// unless i is better for all Y up to N, in which case it becomes new base)
st.push_back({i, N_global + 1});
break;
}
} else {
// Found a valid split. Old is restricted to valid up to 'ans', New takes over before that.
// Wait, stack structure: Top is New, below is Old.
// Top's limit is defined by when Old takes over.
st.push_back({i, ans});
break;
}
}
}
return 1;
}
