#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pb push_back
const int N = 3e7+5;
int lc[N], rc[N], st[N], Ro[N], 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<array<int, 2>> 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;
set<array<int, 2>> A, B;
A.insert({0, n+1});
B.insert({n+1, 0});
auto f = [&](int i1, int i2) {
int L = v[i1][0]+1, R = n, t = n+1;
while (L <= R) {
int m = (L + R)/2;
if (dp[i1] - dp[i2] >= -summ(v[i1][0]+1, v[i2][0], Ro[m-1]))
R = m-1, t = m;
else
L = m+1;
}
return t;
};
for (int i = 1; i < (int)v.size(); ++i) {
while ((*B.begin())[0] <= v[i][0]) {
int X = (*B.begin())[0], Y = (*B.begin())[1];
if (X != (*A.rbegin())[1]) {
B.erase({X, Y});
A.erase({Y, X});
auto it = A.upper_bound({Y, X});
int YY = (*it)[0], XX = (*it)[1];
it--;
A.erase({YY, XX});
B.erase({XX, YY});
int tm = f((*it)[0], YY);
A.insert({YY, tm});
B.insert({tm, YY});
}
else {
B.erase(B.begin());
A.erase({Y, X});
}
}
int p = (*A.rbegin())[0];
dp[i] = dp[p] + sum(v[p][0]+1, v[i][0]-1) + v[i][0] * v[i][1];
if (dp[i] + sum(v[i][0]+1, n) > n) return 0;
int tm = f((*A.rbegin())[0], i);
A.insert({i, tm});
B.insert({tm, i});
}
return 1;
}
