#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define ub(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef pair<int,int> ii;
#define maxn 500005
struct node{
int s,e,m;vector<int> v;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void add(int x,int nv){
v.pb(nv);
if(s==e)return;
if(x<=m)l->add(x,nv);
else r->add(x,nv);
}
void init(){
sort(all(v));
if(s!=e)l->init(),r->init();
}
inline int get(int a,int b){
return ub(v,b)-lb(v,a);
}
int qry(int x,int y,int a,int b){
if(s==x&&e==y)return get(a,b);
if(y<=m)return l->qry(x,y,a,b);
if(x>m)return r->qry(x,y,a,b);
return l->qry(x,m,a,b)+r->qry(m+1,y,a,b);
}
int qryp(int a,int b,int n){
if(s==e)return s;
int g=r->get(a,b);
if(n-g>0){
return l->qryp(a,b,n-g);
}
return r->qryp(a,b,n);
}
}*rt=new node(1,maxn);
void init(int N,int A[],int B[]){
for(int i=0;i<N;++i)rt->add(B[i],A[i]);
rt->init();
}
map<int,int> good;
priority_queue<ii,vector<ii>,greater<ii>> rem;
void create(int i){
auto b=good.find(i);
auto a=prev(b);
int d=b->se-a->se;
int c=rt->qryp(a->fi+1,b->fi,d)+1;
rem.push({c,b->fi});
}
void process(int K){
while(!rem.empty()&&rem.top().fi<=K){
auto[_,i]=rem.top();
rem.pop();
auto it=good.find(i);
if(it==good.end())continue;
auto nit=next(it);
int nx=-1;
if(nit!=good.end())nx=nit->fi;
good.erase(it);
if(nx!=-1)create(nx);
}
}
void insert(int K,int v){
good[K]=v;
if(sz(good)==1)return;
create(K);
}
int can(int M,int K[]){
good.clear();
while(!rem.empty())rem.pop();
sort(K,K+M);
int acc=0;
for(int i=0;i<M;++i){
acc+=K[i];
if(i!=M-1&&K[i]==K[i+1])continue;
process(K[i]);
int dp=rt->qry(K[i],maxn,1,K[i]);
if(!good.empty()){
auto it=--good.end();
dp=min(dp,it->se+rt->qry(K[i],maxn,it->fi+1,K[i]));
}
dp-=acc;
//pf("K: %d, dp: %d\n",K[i],dp);
if(dp<0)return 0;
insert(K[i],dp);
acc=0;
}
return 1;
}
