← 返回题目列表

Codeforces · 1012/A

A. 天空的照片

中文机器翻译题面 查看原题

Pavel 拍了一张他最喜欢的天空星星的照片。他的相机拍摄了天空中属于某个边长与坐标轴平行的矩形的所有点的照片。

严格来说,它会拍摄坐标为 $$$(x, y)$$$ 的所有点的照片,例如 $$$x_1 \leq x \leq x_2$$$ 和 $$$y_1 \leq y \leq y_2$$$,其中 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$是被拍摄矩形的左下角和右上角的坐标。该矩形的面积可以为零。

拍完照片后,Pavel 记下了照片中出现的他最喜欢的明星的 $$$n$$$ 坐标。这些点不一定是不同的,天空的同一点可以有多个星星。

Pavel 最近丢失了他的相机,想买一台类似的。具体来说,他想知道他之前拍摄的照片的尺寸。不幸的是,照片也丢失了。他的笔记也没有多大帮助。数字以随机顺序写在他的记事本上,因此无法分辨哪些数字指定了哪些点的坐标。

Pavel 请你帮助他根据他的笔记确定照片可能的尺寸。由于有多种可能的答案,请找出矩形面积最小的尺寸。

输入

输入的第一行仅包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100\,000$$$),即 Pavel 记录中的点数。

第二行包含 $$$2 \cdot n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_{2 \cdot n}$$$ ($$$1 \leq a_i \leq 10^9$$$),坐标,由 Pavel 按某种顺序写入。

输出

打印唯一的整数,即包含 Pavel 记录中所有点的矩形的最小面积。

示例

输入 #1

4
4 1 3 2 3 2 1 3

输出 #1

1

输入 #2

3
5 8 5 5 7 5

输出 #2

0

注意

在 Pavel 记录中的第一个样本中,星星可以是 $$$(1, 3)$$$、$$$(1, 3)$$$、$$$(2, 3)$$$、$$$(2, 4)$$$。在本例中,包含所有这些点的矩形的最小面积为 $$$1$$$(角点位于 $$$(1, 3)$$$ 和 $$$(2, 4)$$$ 的矩形)。