#include "teams.h"
#include <bits/stdc++.h>
#define maxn 500005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int n;
int a[maxn], b[maxn], prefixSum[maxn], Lef[maxn], Rig[maxn], prefixMax[maxn], secondarySum[maxn];
int it[22*maxn], L[22*maxn], R[22*maxn], root[maxn], nt = 0;
int build(int lo = 1, int hi = n) {
if (lo == hi) return ++nt;
int cur = ++nt, mid = (lo + hi) >> 1;
L[cur] = build(lo, mid);
R[cur] = build(mid+1, hi);
return cur;
}
int upd(int u, int oldver, int lo = 1, int hi = n) {
if (lo == hi) {
it[++nt] = it[oldver] + 1;
return nt;
}
int cur = ++nt, mid = (lo + hi) >> 1;
if (u <= mid) {
L[cur] = upd(u, L[oldver], lo, mid);
R[cur] = R[oldver];
} else {
L[cur] = L[oldver];
R[cur] = upd(u, R[oldver], mid+1, hi);
}
it[cur] = it[L[cur]] + it[R[cur]];
return cur;
}
int get(int u, int v, int r, int lo = 1, int hi = n) {
if (u <= lo && hi <= v) return it[r];
int mid = (lo + hi) >> 1;
return (u <= mid ? get(u, v, L[r], lo, mid) : 0) +
(v > mid ? get(u, v, R[r], mid+1, hi) : 0);
}
vector<int> adj[maxn];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < N; i++) a[i] = A[i];
for (int i = 0; i < N; i++) b[i] = B[i];
for (int i = 0; i < N; i++) adj[a[i]].emplace_back(b[i]);
sort(a, a + N);
sort(b, b + N);
root[0] = build();
for (int i = 1; i <= N; i++) {
root[i] = root[i-1];
for (int j : adj[i]) root[i] = upd(j, root[i]);
}
}
int can(int M, int K[]) {
sort(K, K+M);
int64_t sum = 0;
for (int i = 0; i < M; i++) sum += K[i];
if (sum > n) return 0;
for (int i = 0; i < M; i++) {
prefixSum[i+1] = prefixSum[i] + K[i];
Lef[i+1] = lower_bound(b, b+n, K[i])-b;
Rig[i+1] = n-(upper_bound(a, a+n, K[i])-a);
if (i+1 < M) secondarySum[i+1] = secondarySum[i] + (K[i] + 1 < K[i+1] ? get(K[i] + 1, K[i+1]-1, root[K[i+1]-1]) - get(K[i]+1, K[i+1]-1, root[K[i]]) : 0);
}
prefixMax[0] = INT_MIN;
for (int i = 1; i <= M; i++) prefixMax[i] = max(prefixMax[i-1], Lef[i] - prefixSum[i-1] - secondarySum[i-1]);
int ans = INT_MAX;
for (int i = 1; i <= M; i++) ans = min(ans, n - prefixMax[i] - (Rig[i] + prefixSum[i] + secondarySum[i-1]));
return (ans >= 0);
}
/*
4
1 2
2 3
2 3
2 4
2
2 1 3
2 1 1
*/
