#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 2e6 + 5, BS = 19;
int lc[N*BS], rc[N*BS], st[N*BS], Ro[N*BS], Cn, n;
int build(int l2 = 1, int r2 = n) {
if (l2 == r2) return ++Cn;
int m2 = (l2 + r2)/2, nd = ++Cn;
lc[nd] = build(l2, m2), rc[nd] = build(m2+1, r2);
return nd;
}
int I = 0;
int upd(int nd, vector<int> &f, int l2 = 1, int r2 = n) {
if (l2 == r2) {
int ND = ++Cn; st[ND] = st[nd];
while (I < (int)f.size() && f[I] == l2) st[ND]++, I++;
return ND;
}
int m2 = (l2 + r2)/2, ND = ++Cn;
if (I < (int)f.size() && f[I] <= m2) lc[ND] = upd(lc[nd], f, l2, m2);
else
lc[ND] = lc[nd];
if (I < (int)f.size()) rc[ND] = upd(rc[nd], f, m2+1, r2);
else
rc[ND] = rc[nd];
st[ND] = st[lc[ND]] + st[rc[ND]];
return ND;
}
int sum(int l, int r, int nd, int l2 = 1, int r2 = n) {
if (l <= l2 && r2 <= r) return st[nd];
int m2 = (l2 + r2)/2, S = 0;
if (l <= m2) S += sum(l, r, lc[nd], l2, m2);
if (m2+1 <= r) S += sum(l, r, rc[nd], m2+1, r2);
return S;
}
int sum(int l, int r) {
if (r < l) return 0;
return sum(l, r, Ro[r]);
}
int summ(int l, int r, int nb) {
if (r < l) return 0;
return sum(l, r, nb);
}
void init(int NN, int A[], int B[]) {
n = NN;
Ro[0] = build();
vector<int> a[n+1];
for (int i = 0; i < n; ++i) a[B[i]].pb(A[i]);
for (int i = 0; i < n; ++i) {
I = 0;
sort(a[i+1].begin(), a[i+1].end());
Ro[i+1] = upd(Ro[i], a[i+1]);
}
}
int can(int M, int K[]) {
vector<pair<int, int>> v = {{0, 0}};
long long S = 0;
sort(K, K+M);
for (int i = 0; i < M; ++i) {
long long j = i;
while (i+1 < M && K[i] == K[i+1]) ++i;
v.pb({K[i], (int)(i - j + 1)});
S += K[i] * (i - j + 1);
}
if (S > n) return 0;
int dp[v.size()];
dp[0] = 0;
vector<pair<int, int>> op = {{0, n+1}};
for (int i = 1; i < (int)v.size(); ++i) {
while (op.back().second <= v[i].first) op.pop_back();
int p = op.back().first;
dp[i] = dp[p] + sum(v[p].first+1, v[i].first-1) + v[i].first * v[i].second;
if (dp[i] + sum(v[i].first+1, n) > n) return 0;
int mn = n+1;
for (int j = 0; j < (int)op.size(); ++j) {
int L = v[i].first+1, R = n, t = n+1;
while (L <= R) {
int m = (L + R)/2;
if (dp[op[j].first] - dp[i] >= summ(v[op[j].first].first+1, v[i].first, Ro[m-1]))
R = m-1, t = m;
else
L = m+1;
}
mn = min(mn, t);
}
op.pb({i, mn});
}
return 1;
}
