#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 10;
const int lg = 22;
const int inf = 1e9;
int n, a[maxn], b[maxn], seg[maxn*lg], lc[maxn*lg], rc[maxn*lg], root[maxn], vercnt = 1;
vector<int> val[maxn];
void build(int v, int l, int r){
if (l + 1 == r){
return;
}
lc[v] = vercnt++;
rc[v] = vercnt++;
int mid = (l + r) >> 1;
build(lc[v], l, mid);
build(rc[v], mid, r);
}
void add(int v, int newv, int l, int r, int idx){
if (l + 1 == r){
seg[newv] = seg[v] + 1;
return;
}
int mid = (l + r) >> 1;
if (idx < mid){
lc[newv] = vercnt++;
rc[newv] = rc[v];
add(lc[v], lc[newv], l, mid, idx);
}
else{
lc[newv] = lc[v];
rc[newv] = vercnt++;
add(rc[v], rc[newv], mid, r, idx);
}
seg[newv] = seg[lc[newv]] + seg[rc[newv]];
}
int get(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return seg[v];
int mid = (l + r) >> 1;
return get(lc[v], l, mid, ql, qr)
+ get(rc[v], mid, r, ql, qr);
}
void init(int N, int A[], int B[]){
n = N;
for (int i = 0; i < n; i++){
val[A[i]].push_back(B[i]);
}
root[0] = 0;
build(0, 1, n+1);
for (int i = 1; i <= n; i++){
root[i] = root[i-1];
for (auto x: val[i]){
int tmp = vercnt++;
add(root[i], tmp, 1, n+1, x);
root[i] = tmp;
}
}
}
int k[maxn], dp[maxn], func[maxn << 2];
int f(int idx, int x){
// debug(idx, x, dp[idx], get(root[x], 1, n+1, x, n+1), get(root[k[idx]], 1, n+1, x, n+1));
if (k[idx] > x) return -inf - idx;
return dp[idx] + get(root[x], 1, n+1, x, n+1) - get(root[k[idx]], 1, n+1, x, n+1);
}
vector<int> del;
bool mark[maxn << 2];
void addfunc(int v, int l, int r, int idx){
// debug(v, l, r, idx);
if (!mark[v]){
mark[v] = true;
del.push_back(v);
}
int mid = (l + r) >> 1;
bool L = f(idx, l) < f(func[v], l);
bool M = f(idx, mid) < f(func[v], mid);
if (M){
swap(func[v], idx);
}
// debug(func[v]);
if (l + 1 == r) return;
if (L != M){
addfunc(v << 1, l, mid, idx);
}
else{
addfunc(v << 1 | 1, mid, r, idx);
}
}
int getmin(int v, int l, int r, int idx){
if (l + 1 == r) return f(func[v], idx);
int mid = (l + r) >> 1;
if (idx < mid) return min(f(func[v], idx), getmin(v << 1, l, mid, idx));
else return min(f(func[v], idx), getmin(v << 1 | 1, mid, r, idx));
}
int can(int M, int K[]) {
for (auto x: del){
func[x] = 0;
mark[x] = false;
}
del.clear();
sort(K, K+M);
for (int i = 1; i <= M; i++){
k[i] = K[i-1];
}
dp[0] = 0;
for (int i = 1; i <= M; i++){
dp[i] = getmin(1, 1, n+1, k[i]) - k[i];
// debug(i, dp[i]);
if (dp[i] < 0) return 0;
addfunc(1, 1, n+1, i);
}
return 1;
}
