#include "teams.h"
#include <bits/stdc++.h>
#define N 500005
#define K 100
using namespace std;
struct node{
int l = 0,r = 0;
int val = 0;
}nodes[N * K];
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
int nwnode = ++cnt;
nodes[nwnode] = nodes[v];
if(tl == tr){
nodes[nwnode].val += val;
return nwnode;
}
int tm = (tl + tr)/2;
if(pos <= tm){
if(nodes[v].l == 0){
nodes[v].l = ++cnt;
}
nodes[nwnode].l = upd(nodes[v].l,tl,tm,pos,val);
}
else{
if(nodes[v].r == 0){
nodes[v].r = ++cnt;
}
nodes[nwnode].r = upd(nodes[v].r,tm+1,tr,pos,val);
}
nodes[nwnode].val = nodes[nodes[nwnode].l].val + nodes[nodes[nwnode].r].val;
return nwnode;
}
int get(int v,int tl,int tr,int l,int r){
if(v == 0 || tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return nodes[v].val;
}
int tm = (tl + tr)/2;
return get(nodes[v].l,tl,tm,l,r) + get(nodes[v].r,tm+1,tr,l,r);
}
int root[N];
int n;
vector<int> tmp[N];
void init(int n_, int a[], int b[]) {
n = n_;
for(int i = 0;i<n;i++){
tmp[a[i]].push_back(b[i]);
}
root[0] = upd(1,1,n+1,n+1,n);
for(int i = 1;i<=n+1;i++){
int last = root[i-1];
for(auto u:tmp[i]){
last = upd(last,1,n+1,u,1);
}
last = upd(last,1,n+1,i-1,-get(1,1,n+1,i-1,i-1));
root[i] = last;
}
}
pair<int,int> val[N];
int can(int m, int k[]) {
map<int,int> mp;
sort(k,k+m);
long long sum = 0;
for(int i = 0;i<m;i++){
sum += k[i];
mp[k[i]]++;
}
if(sum > n)return 0;
vector<pair<int,int>> v;
for(auto u:mp){
v.push_back(u);
}
vector<int> st;
for(int x = 0;x<v.size();x++){
int needed = v[x].first * v[x].second;
int tot = 0;
int sum = 0;
int samesum = 0;
int oldsum = 0;
int rp = -1;
int l = v[x].first-1,r = n;
bool ok = 0;
for(int i = st.size()-1;i>=0;i--){
if(val[st[i]].first + 1 < v[x].first)continue;
samesum += val[st[i]].second;
if(rp == -1)rp = st[i];
if(i && val[st[i-1]].first == val[st[i]].first){
continue;
}
if(get(root[v[x].first],1,n+1,v[x].first,val[st[i]].first)- (sum + get(root[rp],1,n+1,l+1,val[st[i]].first) + oldsum) > needed){
int ll = l, rr = val[st[i]].first-1;
while(ll < rr){
int mm = (ll + rr + 1)/2;
if(get(root[v[x].first],1,n+1,v[x].first,mm)- (sum + get(root[rp],1,n+1,l+1,mm) + oldsum) > needed){
rr = mm-1;
}
else ll = mm;
}
l = ll;
ok = 1;
break;
}
sum += oldsum;
sum += get(root[rp],1,n+1,l+1,val[st[i]].first);
l = val[st[i]].first;
oldsum = samesum;
samesum = 0;
rp = -1;
}
if(!ok){
int ll = l, rr = n;
while(ll < rr){
int mm = (ll + rr + 1)/2;
if(get(root[v[x].first],1,n+1,v[x].first,mm)- sum - oldsum> needed){
rr = mm-1;
}
else ll = mm;
}
l = ll;
}
/*
while(l < r){
int m = (l + r + 1)/2;
int now = get(root[v[x].first],1,n+1,v[x].first,m);
for(int i = 0;i<st.size();i++){
if(val[st[i]].first + 1 < v[x].first)break;
if(val[st[i]].first + 1 <= m)
now -= val[st[i]].second;
int p1 = min(val[st[i]].first,m);
int p2 = v[x].first;
if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
if(p1 >= p2)
now -= get(root[st[i]],1,n+1,p2,p1);
}
if(now <= needed){
l = m;
}
else r = m-1;
}*/
tot = get(root[v[x].first],1,n+1,v[x].first,l);
for(int i = 0;i<st.size();i++){
if(val[st[i]].first + 1< v[x].first)break;
if(val[st[i]].first + 1 <= l)
tot -= val[st[i]].second;
int p1 = min(val[st[i]].first,l);
int p2 = v[x].first;
if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
if(p1 >= p2)
tot -= get(root[st[i]],1,n+1,p2,p1);
}
val[v[x].first] = {l,needed-tot};
while(st.size() && val[st.back()].first < val[v[x].first].first){
st.pop_back();
}
st.push_back(v[x].first);
if(val[v[x].first].first == n && val[v[x].first].second)return 0;
}
return 1;
}
