#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e5+5;
int n, dp[nx], pos[nx], need[nx];
vector<int> cmp[nx];
struct persist
{
struct node
{
int f;
node *l, *r;
node(): f(0), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &k)
{
k=new node();
if (l==r) return;
int md=(l+r)/2;
build(l, md, k->l);
build(md+1, r, k->r);
}
void update(int l, int r, pnode &k, pnode p, int idx)
{
k=new node(*p);
if (l==r) return k->f++, void();
int md=(l+r)/2;
if (idx<=md) update(l, md, k->l, p->l, idx);
else update(md+1, r, k->r, p->r, idx);
k->f=k->l->f+k->r->f;
}
int query(int l, int r, pnode k, pnode p, int idx)
{
if (r<idx) return 0;
if (idx<=l) return k->f-p->f;
int md=(l+r)/2;
return query(l, md, k->l, p->l, idx)+query(md+1, r, k->r, p->r, idx);
}
} s;
void init(int N, int A[], int B[]) {
n=N;
for (int i=0;i <n; i++) cmp[A[i]].push_back(B[i]);
s.build(1, n, s.rt[0]);
for (int i=1; i<=n; i++)
{
s.rt[i]=s.rt[i-1];
for (auto x:cmp[i]) s.update(1,n , s.rt[i], s.rt[i], x);
}
}
struct range
{
int l, r, p;
range(int l=0, int r=0, int p=0): l(l), r(r), p(p){}
};
int cost(int pv, int x)
{
return dp[pv]+s.query(1, n, s.rt[x], s.rt[pos[pv]], x);
}
int can(int M, int K[]) {
map<int, int> mp;
int sm=0, t=0;
for (int i=0; i<M; i++)
{
sm+=K[i];
mp[K[i]]+=K[i];
if (sm>n) return 0;
}
int sz=mp.size(), mn=0;
for (int i=1; i<=sz; i++) dp[i]=INT_MAX;
for (auto &[x, y]:mp) t++, pos[t]=x, need[t]=y;
deque<range> dq;
dq.push_back(range(1, n, 0));
for (int i=1; i<=sz; i++)
{
dp[i]=min(dp[i], cost(dq.front().p, i)-need[i]);
//for (auto x:dq) cout<<"dq "<<x.l<<' '<<x.r<<' '<<x.p<<'\n';
//cout<<"debug "<<i<<' '<<dp[i]<<'\n';
if (dq.front().r==pos[i]) dq.pop_front();
else dq.front().l++;
while (!dq.empty()&&cost(dq.front().p, dq.front().r)>=cost(i, dq.front().r)) dq.pop_front();
if (dq.empty()) dq.push_back(range(pos[i]+1, n, i));
else
{
int l=dq.front().l, r=dq.front().r;
while (l<r)
{
int md=(l+r)/2;
if (cost(dq.front().p, md)<cost(i, md)) r=md;
else l=md+1;
}
dq.front().l=l;
if (dq.front().l!=pos[i]+1) dq.push_front(range(pos[i]+1, dq.front().l-1, i));
}
mn=min(mn, dp[i]);
}
return mn>=0;
}
