Паша сделал фото своих любимых звёзд на небе. Его камера сфотографировала все звёзды на небе, которые лежали в некотором прямоугольнике со сторонами, параллельными осям координат.
Более формально, она сделала фотографию всех точек с координатами $$$(x, y)$$$, для которых выполнено $$$x_1 \leq x \leq x_2$$$ и $$$y_1 \leq y \leq y_2$$$, где $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ — координаты левого нижнего и правого верхнего прямоугольника, который фотографируют. Площадь фотографируемого прямоугольника может быть нулевой.
Сразу после фотографирования Паша выписал в блокнот координаты $$$n$$$ своих любимых звёзд, попавших на фото. Эти точки не обязательно различны, так как в одной точке неба может быть несколько звёзд.
Но потом, к сожалению, Павел потерял свою камеру и хочет купить новую, похожую на предыдущую. В частности, он хочет знать размер фотографии, снятой ранее. К сожалению, эта фотография тоже оказалась утеряна. Его записи в блокноте сохранились, но не осообо помогают — все координаты оказались перемешаны и невозможно определить, каким точкам соответствуют.
Паша попросил вас определить, каков мог быть размер фотографии, не противоречащей его записям.
Так как может быть несколько различных ответов, найдите размер фотографии с минимальной площадью.
В первой строке входных данных находится одно целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$)— количество точек, координаты которых выписал Паша.
Во второй строке находятся $$$2 \cdot n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_{2 \cdot n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — все координаты, выписанные Пашей, в каком-то порядке.
Выведите единственное число — минимальную площадь прямоугольника, который мог содержать все звёзды в записях Паши.
4
4 1 3 2 3 2 1 3
1
3
5 8 5 5 7 5
0
В первом тестовом примере точки из записей Павла могут быть равными $$$(1, 3)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$. В таком случае, минимальная площадь прямоугольника, который их содержит равна $$$1$$$ (прямоугольник с вершинами в $$$(1, 3)$$$ и $$$(2, 4)$$$).
Название |
---|