#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 5e5 + 5;
int n;
struct Node{
int cnt, lc, rc;
Node(){
cnt = 0;
}
};
vector<Node>st;
void build(int id, int l, int r){
if(l < r){
int m = (l + r) >> 1;
st[id].lc = st.size();
st.push_back(Node());
st[id].rc = st.size();
st.push_back(Node());
build(st[id].lc, l, m);
build(st[id].rc, m + 1, r);
}
}
void update(int id, int l, int r, int p){
st[id].cnt++;
if(l < r){
int m = (l + r) >> 1;
if(m < p){
st.push_back(st[st[id].rc]);
update(st[id].rc = int(st.size()) - 1, m + 1, r, p);
}
else{
st.push_back(st[st[id].lc]);
update(st[id].lc = int(st.size()) - 1, l, m, p);
}
}
}
int get(int id, int right_bound){
int l = 0, r = lim, ans = 0;
while(l < r){
int m = (l + r) >> 1;
if(m <= right_bound){
ans += st[st[id].lc].cnt;
id = st[id].rc;
l = m + 1;
}
else{
id = st[id].lc;
r = m;
}
}
return ans;
}
void init(int _n, int a[], int b[]){
st.assign((n = _n) + 2, Node());
build(n + 1, 0, lim);
vector<vector<int>>add(n + 1);
for(int i = 0; i < n; i++){
add[a[i]].push_back(b[i]);
}
for(int i = n; i > 0; i--){
st[i] = st[i + 1];
for(int& j : add[i]){
update(i, 0, lim, j);
}
}
}
int can(int m, int k[]){
if(accumulate(k, k + m, 0) > n){
return 0;
}
sort(k, k + m);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
set<pair<int, int>>s;
s.insert(make_pair(0, 0));
auto calc = [&] (pair<int, int>p1, pair<int, int>p2){
int x1 = p1.second, x2 = p2.second;
int id1 = p1.first + 1, id2 = p2.first + 1, l = 0, r = lim;
while(l < r){
int m = (l + r) >> 1;
if(p1.second + st[st[id1].lc].cnt < p2.second + st[st[id2].lc].cnt){
l = m + 1;
p1.second += st[st[id1].lc].cnt;
p2.second += st[st[id2].lc].cnt;
id1 = st[id1].rc;
id2 = st[id2].rc;
}
else{
r = m;
id1 = st[id1].lc;
id2 = st[id2].lc;
}
}
return l + 1;
};
for(int i = 0; i < m; ){
int cur = k[i], cnt = 0;
while(i < m && cur == k[i]){
cnt += k[i++];
}
while(!pq.empty()){
auto [time, p] = pq.top();
if(time > cur){
break;
}
pq.pop();
auto it = s.lower_bound(make_pair(p, -1));
if(it == s.end() || it->first != p){
continue;
}
if(it != s.begin() && next(it) != s.end()){
pq.push(make_pair(calc(*prev(it), *next(it)), next(it)->first));
}
s.erase(it);
}
int x = s.rbegin()->second + get(s.rbegin()->first + 1, cur - 1) + cnt;
for(auto& [p, val] : s){
maximize(x, val + get(p + 1, cur - 1) + cnt);
}
if(x + get(cur + 1, n) > n){
return 0;
}
pq.push(make_pair(calc(*s.rbegin(), make_pair(cur, x)), cur));
s.insert(make_pair(cur, x));
}
return 1;
}
