#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[500009],dp[500009],k[500009],za,l,r,z,zz,g[500009],G[500009],K;
pair <int, int> p[500009];
multiset <int> s;
multiset <int>::iterator it,tt,TT;
multiset <pair <int, int> > h;
multiset <pair <int, int> >::iterator IT;
vector <int> v[1200009],pr[1200009];
void bld(int q, int w, int rr){
if(q>=w) return;
int mid=(q+w)/2;
pr[rr].resize(v[rr].size());
v[rr*2].push_back(0);v[rr*2+1].push_back(0);
for(int h=1; h<v[rr].size(); h++){
pr[rr][h]=pr[rr][h-1];
if(p[v[rr][h]].second<=mid){
pr[rr][h]++;
v[rr*2].push_back(v[rr][h]);
}else{
v[rr*2+1].push_back(v[rr][h]);
}
}
bld(q,mid,rr*2);
bld(mid+1,w,rr*2+1);
}
void read(int q, int w, int rr, int L, int R){
if(q>w) return;
if(L>R) return;
if(q>=l&&w<=r){
z+=R-L+1;
return;
}
read(q,(q+w)/2,rr*2,pr[rr][L-1]+1,pr[rr][R]);
read((q+w)/2+1,w,rr*2+1,((L-1)-pr[rr][L-1])+1,(R-pr[rr][R]));
}
void read2(int q, int w, int rr, int L, int R){
if(q>w||L>R||K<=0) return;
if(R-L+1<=K){
K-=R-L+1;
z=p[v[rr][R]].second;
return;
}
if(q==w){
z=q;K=0;
return;
}
read2(q,(q+w)/2,rr*2,pr[rr][L-1]+1,pr[rr][R]);
read2((q+w)/2+1,w,rr*2+1,((L-1)-pr[rr][L-1])+1,(R-pr[rr][R]));
}
int W(int q, int w){
if(dp[q]<=dp[w]) return 0;
int qw=0,we=0;
qw=lower_bound(p+1,p+b+1,make_pair(q,0))-p;
we=lower_bound(p+1,p+b+1,make_pair(w+1,0))-p-1;
if(qw+1>we) return a+3;
l=1;r=w-1;z=0;
read(1,za,1,qw+1,b);
K=z+dp[q]-dp[w];
z=0;
read2(1,za,1,qw+1,we);
if(K>0){
return a+3;
}
return z;
}
int cost(int q, int w){
int qw=0;
qw=lower_bound(p+1,p+b+1,make_pair(q+1,0))-p-1;
if(qw<=0) return 0;
l=w;r=b;z=0;
read(1,za,1,1,qw);
return z;
}
void init(int Nn, int Aa[], int Bb[]) {
b=Nn;
for(i=1; i<=b; i++){
p[i].first=Aa[i-1];p[i].second=Bb[i-1];
k[p[i].first]++;k[p[i].second+1]--;
}
for(i=1; i<=b; i++) k[i]+=k[i-1];
sort(p+1,p+b+1);
za=1;
while(za<b) za*=2;
v[1].push_back(0);
for(i=1; i<=b; i++){
v[1].push_back(p[i].second);
}
bld(1,za,1);
}
int can(int Mm, int Kk[]) {
a=Mm;zx=0;
for(i=1; i<=a; i++){
G[i]=Kk[i-1];zx+=G[i];
}
sort(G+1,G+a+1);
if(zx>b){
return 0;
}
c=0;
for(i=1; i<=a; i++){
if(f[c]==G[i]){
g[c]++;
}else{
c++;f[c]=G[i];g[c]=1;
}
}
a=c;
for(i=1; i<=a; i++){
dp[i]=k[f[i]]-f[i]*g[i];
e=0;
if(s.size()!=0){
it=s.end();it--;
if(W((*it),i-1)<=i){
e=1;
}
}
if(e==0){
s.insert(i-1);
if(s.size()>1){
it=s.end();it--;it--;
c=W((*it),i-1);
h.insert({c,(*it)});
}
}
while(h.size()){
IT=h.begin();
if((*IT).first>i) break;
it=s.lower_bound((*IT).second);tt=it;tt++;
h.erase(IT);
TT=tt;TT++;
if(TT!=s.end()){
c=W((*tt),(*TT));
h.erase(h.lower_bound({c,(*tt)}));
c=W((*it),(*TT));
h.insert({c,(*it)});
}
s.erase(tt);
}
if(s.size()!=0){
it=s.end();it--;
zx=dp[(*it)]-cost(f[j],f[i])+(k[f[i]]-f[i]*g[i]);
if(dp[i]>zx) dp[i]=zx;
}
}
zx=0;
for(i=1; i<=a; i++){
zx=min(zx,dp[i]);
}
if(zx>=0) return 1; else return 0;
}
