#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];
int cost(int q, int w);
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>r||w<l) return;
//cout<<q<<" "<<w<<" "<<rr<<" "<<L<<" "<<R<<"\n";
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;
//cout<<q<<" "<<w<<" "<<rr<<" "<<L<<" "<<R<<"\n";
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 AS=0,SD=0;
AS=dp[q];SD=dp[w]-k[f[w]]+cost(f[q],f[w]);
//cout<<AS<<" "<<SD<<"\n";
if(AS<=SD) return 0;
int qw=0,we=0;
qw=lower_bound(p+1,p+b+1,make_pair(f[q]+1,0))-p;
we=lower_bound(p+1,p+b+1,make_pair(f[w]+1,0))-p-1;
if(qw>we) return b+3;
//cout<<q<<" "<<w<<" "<<qw<<" "<<we<<"\n";
l=1;r=f[w]-1;z=0;
//cout<<l<<" "<<r<<" "<<qw<<" "<<b<<"\n";
read(1,za,1,qw,b);
//cout<<z<<"\n";
//exit(0);
//K=z+dp[q]-dp[w];
K=z+AS-SD;
z=0;
read2(1,za,1,qw,we);
if(K>0){
return b+3;
}
return z+1;
}
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(i);
}
bld(1,za,1);
}
void print(){
cout<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<"\n";
cout<<"s: ";
for(it=s.begin(); it!=s.end(); it++){
cout<<(*it)<<" ";
}
cout<<"\n";
cout<<"h: ";
for(IT=h.begin(); IT!=h.end(); IT++){
cout<<(*IT).first<<" "<<(*IT).second<<" ";
}
cout<<"\n";
}
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;
//
/*cout<<a<<endl;
for(i=1; i<=a; i++){
cout<<f[i]<<" "<<g[i]<<"\n";
}*/
//
//cout<<"cost: "<<cost(3,5)<<"\n";
//
dp[1]=-1;dp[2]=0;
//cout<<W(1,2)<<"\n";
//exit(0);
//
s.clear();h.clear();
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)<=f[i]){
e=1;
}
}
if(i==1) 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>f[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[(*it)],f[i])+(k[f[i]]-f[i]*g[i]);
if(dp[i]>zx) dp[i]=zx;
}
/*if(i==3){
cout<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<"\n";
cout<<"s: ";
for(it=s.begin(); it!=s.end(); it++){
cout<<(*it)<<" ";
}
cout<<"\n";
cout<<"h: ";
for(IT=h.begin(); IT!=h.end(); IT++){
cout<<(*IT).first<<" "<<(*IT).second<<" ";
}
cout<<"\n";
exit(0);
}*/
}
zx=0;
for(i=1; i<=a; i++){
zx=min(zx,dp[i]);
}
/*for(i=1; i<=a; i++) cout<<dp[i]<<" ";
cout<<"\n";*/
if(zx>=0) return 1; else return 0;
}
