题目描述

最近部门要选两个员工去参加一个需要合作的知识竞赛，每个员工均有一个推理能力值 $A_{i}$，以及一个阅读能力值 $B_{i}$。如果选择第 $\mathit i$ 个人和第 $\mathit j$ 个人去参加竞赛，那么他们在阅读方面所表现出的能力为 $X=\frac{(B_{i}+B_{j})}{2}$，他们在推理方面所表现出的能力为 $Y=\frac{(A_{i}+A_{j})}{2}$。

现在需要最大化他们表现较差一方面的能力，即让 $\mathit min(X,Y)$ 尽可能大，问这个值最大是多少。

进阶：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$

输入格式

第一行一个正整数 $\mathit n$，代表员工数。

接下来 $\mathit n$ 行每行两个正整数 $A_{i},B_{i}$，分别用来描述第 $\mathit i$ 个员工的推理和阅读能力。

$2 \leq n \leq 2×10^{5}$

$1 \leq A_{i},B_{i} \leq 10^{8}$

输出格式

仅一行一个一位小数用来表示答案。

示例1

3
2 2
3 1
1 3

2.0

说明：

选择第一个和第二个员工或第一个和第三个时，较差方面的能力都是 $\text 1.5$，选择第二个和第三个时较差方面能力是 $\text 2$。