AT_arc121_a [ARC121A] 2nd Greatest Distance

# [ARC121A] 2nd Greatest Distance 在二维平面上有 $N$ 个使用编号 $1$ 到 $N$ 的数字标记的房子。 房子 $i$ 位于 $(x_i,y_i)$。 房子 $i,j$ 之间的距离是 $\max(\left|{x_i-x_j}\right|, \left|{y_i-y_j}\right|)$。 有总共 $N(N-1)/2$ 对不同的房子，对于每一对不同的房子，计算它们之间的距离，把距离值按降序排列成一个长度为 $N(N-1)/2$ 的数列。请输出这个数列的第二个数字。

> $N$ $x_{1}$ $y_{1}$ $\ldots$ $x_{N}$ $y_{N}$

对于每一个样例，输出第二大的数字。

### 样例输入 #1 ``` 3 0 0 1 2 4 0 ``` ### 样例输出 #1 ``` 3 ``` ### 样例输入 #2 ``` 4 0 0 0 0 1 0 0 1 ``` ### 样例输出 #2 ``` 1 ``` ### 样例输入 #3 ``` 20 407 361 167 433 756 388 -551 -47 306 -471 36 928 338 -355 911 852 288 70 -961 -769 -668 -386 -690 -378 182 -609 -677 401 -458 -112 184 -131 -243 888 -163 471 -11 997 119 544 ``` ### 样例输出 #3 ``` 1766 ``` - 所有的输入都保证为整数 - $3 \leqslant N \leqslant 2 \times 10^5$ - $-10^9 \leqslant x_i, y_i \leqslant 10^9$