#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define pb push_back
const int N = 2e6 + 5, BS = 25;
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]);
}
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<array<int, 2>> v;
long long t = 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)});
t += K[i] * (i - j + 1);
}
if (t > n) return 0;
int dp[v.size()];
dp[0] = v[0][1]*v[0][0] + sum(1, v[0][0] - 1);
if (dp[0] + sum(v[0][0]+1, n) > n) return 0;
for (int i = 1; i < (int)v.size(); ++i) {
dp[i] = sum(1, v[i][0]-1);
for (int j = 0; j < i; ++j) dp[i] = max(dp[i], dp[j] + sum(v[j][0]+1, v[i][0]-1));
dp[i] += v[i][0] * v[i][1];
if (dp[i] + sum(v[i][0]+1, n) > n) return 0;
}
return 1;
}
