#include <bits/stdc++.h>
#include "teams.h"
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
const int Nn = 5e5 + 5;
bool used[Nn];
int n, m, cost, a[Nn], b[Nn], k[Nn], dp[Nn], pr[Nn], nx[Nn], mpr[Nn];
vector < int > v[4* Nn], O[Nn];
void build(tree) {
if (l == r) {
v[h] = O[l];
return;
}
build(left), build(right);
int li = 0, ri = 0, ls = v[lf].size(), rs = v[rf].size();
while (li < ls || ri < rs) {
if (li < ls && (ri == rs || v[lf][li] <= v[rf][ri])) {
v[h].pb(v[lf][li++]);
}
else
if (ri < rs && (li == ls || v[rf][ri] <= v[lf][li])) {
v[h].pb(v[rf][ri++]);
}
}
}
int Mn, Mx, id;
int g(int h) {
int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
return max(0, r - l);
}
int get(tree) {
if (l == r) return g(h);
if (Mx <= mf) return get(left) + g(rf);
return get(right);
}
int Get(tree, int vl) {
if (l == r) {
if (g(h) <= vl) return l;
return n + 1;
}
int rc = g(rf);
if (rc <= vl)
return min(mf + 1, Get(left, vl - rc));
return Get(right, vl);
}
int Mm(int tl, int tr) {
Mn = k[tl] + 1, Mx = k[tr];
return Get(1, 1, n, dp[tr] - dp[tl]);
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; ++i) {
a[i] = A[i - 1];
b[i] = B[i - 1];
O[b[i]].pb(a[i]);
}
for (int i = 1; i <= n; ++i) {
sort(O[i].begin(), O[i].end());
}
build(1, 1, n);
}
int can(int M, int K[]) {
m = M;
ll sum = 0;
for (int i = 1; i <= m; ++i) {
pr[i] = nx[i] = used[i] = 0;
k[i] = K[i - 1];
sum += k[i];
}
sort(k + 1, k + m + 1);
if (sum > n) return 0;
set < pair < int , int > > st;
vector < int > dq;
dq.push_back(0);
for (int i = 1; i <= m; ++i) {
while (st.size() && (*st.begin()).f <= k[i]) {
int mo = (*st.begin()).f;
int id = (*st.begin()).s;
st.erase(st.find({mo, id}));
used[id] = true;
int tl = pr[id], tr = nx[id];
if (tr) {
st.erase({mpr[tr], tr});
mpr[tr] = Mm(tl, tr);
st.insert({mpr[tr], tr});
nx[tl] = tr, pr[tr] = tl;
}
}
while (used[dq.back()]) {
dq.pop_back();
}
int l = dq.back();
Mn = k[l] + 1, Mx = k[i];
dp[i] = dp[l] - k[i] + get(1, 1, n);
if (dp[i] < 0) return false;
dq.push_back(i);
mpr[i] = Mm(l, i);
pr[i] = l, nx[l] = i;
st.insert({mpr[i], i});
}
return true;
}
