#include <fstream>
#include <algorithm>
using namespace std;
//Marimea arborelui de intervale
#define marime 262144
//Numarul de puncte date
int n;
//Un nod din arborele de intervale
struct nod
{
int st,dr;
int sum_s; //Numarul de puncte de deasupra liniei de baleere (voi transpune sistemul de coordonate prin relatia (x,y) devine (y,x), astfel linia verticala ce trebuie trasa la inceput va deveni o linie orizontala)
int sum_j; //Numarul de puncte de dedesubtul liniei de baleere
int best; //Cel mai mic numar de puncte obtinute prin suma NV+SE ce se poate obtine ducand o linie verticala pe langa cea orizontala deja trasa
}arb[marime];
//Un punct citit de la tastatura
struct punct
{
int x,y;
}v[100005];
//Punctele normalizate vor fi sortate descrescator dupa y si, in caz de egalitate, crescator dupa x
bool operator<(const punct &a,const punct &b)
{
if(a.y>b.y)
return 1;
else if(a.y==b.y)
if(a.x<b.x)
return 1;
return 0;
}
//Aceasta structura va tine un element normalizat
struct aux
{
int val; //Valoarea sa din vectorul v
int ind; //Pozitia pe care s afla
}x[100005],y[100005];
//Se compara doua valori
bool operator<(const aux &a,const aux &b)
{
if(a.val<b.val)
return 1;
return 0;
}
//Minimul dintre doua numere
int minim(int a,int b)
{
if(a<b)
return a;
return b;
}
//Functia reface nodul a pe baza nodurilor b si c (va reface doar best-ul, nu si sum-urile)
void calc_best(nod &a,nod b,nod c)
{
int v1=b.best+c.sum_s;
int v2=c.best+b.sum_j;
a.best=minim(v1,v2);
}
//Functia construieste arborele initial
void build(int st,int dr,int poz)
{
arb[poz].st=st;
arb[poz].dr=dr;
arb[poz].best=0;
arb[poz].sum_s=0;
arb[poz].sum_j=0;
if(st==dr)
return;
int mijl=(st+dr)>>1;
build(st,mijl,poz<<1);
build(mijl+1,dr,(poz<<1)+1);
}
//Functia face un update cu valoarea val in sus/jos pozitia unde in arborele de intervale
void update(int unde,bool sus,int val,int poz)
{
//Daca avem un singur element
if(arb[poz].st==arb[poz].dr && arb[poz].st==unde)
{
if(sus)
arb[poz].sum_s+=val;
else
arb[poz].sum_j+=val;
arb[poz].best=arb[poz].sum_s+arb[poz].sum_j;
return;
}
//Daca avem mai multe
int mijl=(arb[poz].st+arb[poz].dr)>>1;
if(unde<=mijl)
update(unde,sus,val,poz<<1);
else
update(unde,sus,val,(poz<<1)+1);
if(sus)
arb[poz].sum_s+=val;
else
arb[poz].sum_j+=val;
calc_best(arb[poz],arb[poz<<1],arb[(poz<<1)+1]);
}
int main()
{
//Deschiderea fisierelor de intrare si iesire
ifstream cin("cadrane.in");
ofstream cout("cadrane.out");
//Iteratori
int i,j;
//Citim punctele initiale
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i].y>>v[i].x;
y[i].val=v[i].y;
y[i].ind=i;
x[i].val=v[i].x;
x[i].ind=i;
}
//Sortam vectorii de normalizare
sort(y+1,y+n+1);
sort(x+1,x+n+1);
//Realizam normalizarea propriu-zisa
int cat1=1;
int cat2=1;
v[y[1].ind].y=1;
v[x[1].ind].x=1;
x[0]=x[1];
y[0]=y[1];
for(i=1;i<=n;i++)
{
if(y[i].val!=y[i-1].val)
cat2++;
if(x[i].val!=x[i-1].val)
cat1++;
v[y[i].ind].y=cat2;
v[x[i].ind].x=cat1;
}
//Sortam punctele normalizate
sort(v+1,v+n+1);
build(1,n,1);
//Acum coordonatele punctelor sunt normalizate si sortate deci putem incepe baleerea (initial toate punctele sunt sub linia de baleere)
for(i=1;i<=n;i++)
update(v[i].x,0,1,1);
//Maxim va fi chiar raspunsul problemei
int maxim=-1;
//Aici vom retine punctele ce trebuie sterse din partea de sus (atentie la punctele ce se afla pe linia de baleere, trebuie luate ca fiind si sus si jos, deci trebuie ca, dupa ce problema in starea curenta a liniei este analizata, sa stergem punctele ce au fost adaugate jos)
int retin[100005];
//Baleerea propriu-zisa
i=1;
while(i<=n)
{
//Adaugam sub linie punctele de pe linia de baleere
j=0;
do
{
update(v[i].x,1,1,1);
retin[j++]=i;
i++;
if(i>n)
break;
}
while(v[i].y==v[i-1].y);
//Updatam maximul
if(arb[1].best>maxim)
maxim=arb[1].best;
//Stergem punctele de pe linia de baleere de sus
while(j>0)
update(v[retin[--j]].x,0,-1,1);
}
//Afisam maximul
cout<<maxim<<'\n';
//Inchiderea fisierelor de intrare si iesire
cin.close();
cout.close();
return 0;
}