题目背景

本题与 银组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 10^5$）散布在整个农场上。整个农场是一个无限大的二维平面，第 $i$ 头奶牛的坐标是 $(x_i,y_i)$（保证 $x_i,y_i$ 均为正奇数，且 $x_i,y_i \leq 10^6$），且没有任意两头奶牛在同一位置上。

FJ 希望修建一条竖直方向的栅栏，它的方程是 $x=a$，他还希望修建一条水平方向的栅栏，它的方程是 $y=b$。为了防止栅栏经过奶牛，$a,b$ 均要求是偶数。容易发现，这两个栅栏会在 $(a,b)$ 处相交，将整个农场分割为四个区域。

FJ 希望这四个区域内的奶牛数量较为均衡，尽量避免一个区域奶牛多而另一个区域奶牛少的情况。令 $M$ 为四个区域里奶牛最多区域的奶牛数量，请帮 FJ 求出 $M$ 的最小值。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $x_i,y_i$，描述第 $i$ 头奶牛的位置。

输出格式

输出 $M$ 的最小值。

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

2