#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// 定義最大值
const int MAXN = 500005;
// 線段樹節點
struct Node {
int sum;
int l, r;
} tree[MAXN * 25];
int roots[MAXN];
int node_cnt = 0;
int N_val;
// 建樹
int build(int l, int r) {
int u = ++node_cnt;
tree[u].sum = 0;
if (l == r) return u;
int mid = (l + r) >> 1;
tree[u].l = build(l, mid);
tree[u].r = build(mid + 1, r);
return u;
}
// 更新
int update(int prev, int l, int r, int pos) {
int u = ++node_cnt;
tree[u] = tree[prev];
tree[u].sum++;
if (l == r) return u;
int mid = (l + r) >> 1;
if (pos <= mid) tree[u].l = update(tree[prev].l, l, mid, pos);
else tree[u].r = update(tree[prev].r, mid + 1, r, pos);
return u;
}
// 查詢區間 [ql, qr] 的和
int query(int u, int v, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[u].sum - tree[v].sum;
int mid = (l + r) >> 1;
return query(tree[u].l, tree[v].l, l, mid, ql, qr) +
query(tree[u].r, tree[v].r, mid + 1, r, ql, qr);
}
struct Student {
int a, b;
} p[MAXN];
bool cmp(Student x, Student y) {
return x.a < y.a;
}
// 初始化
void init(int N, int A[], int B[]) {
N_val = N;
for (int i = 0; i < N; i++) {
p[i] = {A[i], B[i]};
}
sort(p, p + N, cmp);
roots[0] = build(1, N);
int cur = 0;
for (int i = 1; i <= N; i++) {
roots[i] = roots[i - 1];
while (cur < N && p[cur].a == i) {
roots[i] = update(roots[i], 1, N, p[cur].b);
cur++;
}
}
}
// 獲取在 A 範圍 [1, x] 內，且 B 範圍 [y1, y2] 內的學生數
int count_range(int x, int y1, int y2) {
if (y1 > y2) return 0;
return query(roots[x], roots[0], 1, N_val, y1, y2);
}
// 驗證函數
int can(int M, int K[]) {
sort(K, K + M);
// Stack 元素: {k_value, b_limit, accumulated_usage}
// k_value: 該層的隊伍人數限制
// b_limit: 該層隊伍佔用的學生 B 值下界 (即該層隊伍使用的是 [b_limit, ???] 的學生)
// 我們要維護一個階梯形狀，越上面的層，K 越大，b_limit 也應該越大 (Greedy: 大 K 用大 B)
struct Element {
int k;
int b; // split point
int val; // number of students used by this block plus previous blocks basically
};
vector<Element> st;
for (int i = 0; i < M; i++) {
int k = K[i];
// 1. 如果當前 stack 頂部的 k 相同，可以簡單視為需求增加，
// 但為了通用邏輯，我們每次都當作新的塊處理。
// 我們需要刪掉 stack 中無法支撐 k 的部分
// 也就是說，如果我們要在 k 處建立新塊，之前 stack 頂部如果 b < k，
// 那些 b < k 的學生對當前 k 是無效的，但對 stack 內層是有效的。
// 然而這裡我們不需要手動刪，因為查詢 count_range(k, ...) 自然會過濾掉 A > k 的情況?
// 不，count_range 過濾的是 A。這裡 B 的過濾是透過 b_limit。
// Greedy: 我們總是優先用 B 小的。
while (!st.empty() && st.back().k >= k) {
// 這種情況在 K 排序後一般不會發生 (除非有重複 K，或者邏輯反了)
// 因為我們 K 是從小到大處理的。
st.pop_back();
}
// 需要的人數
int needed = k;
// 開始回溯 Stack，找到合適的 b_limit
while (!st.empty()) {
Element top = st.back();
// 計算從 top.b 到 N，在 A <= k 的條件下有多少人
// 減去 之前層級已經佔用的人數 (top.val)
// 實際上 top.val 存的是 "在 top.b 以上被 top 及其底下的層佔用的人數"
// 計算：在 [top.b, N] 範圍內，滿足 A <= k 的人 - 滿足 A <= top.k 的人 (這些是新增的潛力股) ??
// 不太對。標準公式是：
// 我們想找一個位置 b_new > top.b，使得 [b_new, N] 內的可用學生數剛好滿足 (needed + stack_usage)
int diff = count_range(k, top.b, N_val) - count_range(top.k, top.b, N_val);
// 這裡的邏輯是：在 (top.k, k] 的 A 區間內，且 B >= top.b 的學生是 "額外多出來的資源"
// 如果這些資源 + top 這一層剩餘的空間 < needed，那 top 層就撐不住了，要合併。
// 正確的維護值：st[i].val = count_range(st[i].k, st[i].b, N_val) - (被 i 之前層用掉的)
int cnt = count_range(k, top.b, N_val);
if (cnt - top.val < needed) {
// 餘裕不足，需要吃掉這一層
needed += top.val - count_range(top.k, top.b, N_val); // 回補這一層原本承諾的貢獻
st.pop_back();
} else {
break;
}
}
// 二分搜尋新的 b_start
// 搜索範圍：如果 stack 為空，範圍是 [1, N+1]，否則 [st.back().b, N+1]
// 我們要找最大的 b_new 使得 count(k, b_new, N) - (stack adjustments) >= needed
int low = st.empty() ? 1 : st.back().b;
int high = N_val + 1;
int base_sub = st.empty() ? 0 : st.back().val;
int base_cnt = st.empty() ? 0 : count_range(st.back().k, st.back().b, N_val);
int limit_val = needed + (base_cnt - base_sub);
// 這樣就很清楚了。我們在 [low, N+1] 裡二分搜 b_new。
// 使得 calc_diff(b_new) >= calc_diff(low) - needed 的最大 b_new (保留越多越好? 不，是剛好滿足)。
// 實際上，因為 calc_diff 是隨 b 遞減的 (b 越大，count 越小)。
// 所以 `calc_diff(low) - needed` 是一個目標值 Target。
// 我們要找 b 使得 `calc_diff(b) >= Target` 的最大 b。
// 如果連 calc_diff(low) < Target (即 needed < 0，不可能)，或者 calc_diff(N+1) > Target (不可能)。
// 找到 b_new 後，如果 b_new > N，表示學生不夠 (需要吃到 N 以後)。
int target = (count_range(k, low, N_val) - count_range(st.empty()?0:st.back().k, low, N_val) + (st.empty()?0:st.back().val)) - needed;
int search_l = low, search_r = N_val + 1;
int ans_b = -1;
while(search_l <= search_r) {
int mid = (search_l + search_r) >> 1;
int val_mid = count_range(k, mid, N_val) - count_range(st.empty()?0:st.back().k, mid, N_val) + (st.empty()?0:st.back().val);
if(val_mid >= target) {
ans_b = mid;
search_l = mid + 1; // 嘗試找更大的 b (保留更少的餘量，也就是吃掉更多? 不，val_mid >= target 代表餘量夠大)
} else {
search_r = mid - 1;
}
}
if (ans_b == -1 || ans_b > N_val) {
// 這裡有個 edge case，如果 ans_b 跑出去了，但實際上在 N+1 處 val 為 0。
// 如果 target < 0，那即使吃到 N+1 也不夠。
return 0;
}
// 找到了 b_new = ans_b
// 新的 val 就是 target (或者 ans_b 處的實際 val)
int new_val = count_range(k, ans_b, N_val) - count_range(st.empty()?0:st.back().k, ans_b, N_val) + (st.empty()?0:st.back().val);
st.push_back({k, ans_b, new_val});
}
return 1;
}
int main() {
// 範例測試 (實際提交時不需要 main，或是根據 OJ 要求)
// 這裡只是示意
return 0;
}
