Конвейер и опасная пара

На заводе детали проходят через участок сборки: их нужно разложить по коробкам по две штуки.

Если в одной коробке лежат детали размеров x и y, то «опасность» коробки равна x·y (произведение). За смену инженер смотрит на самую опасную коробку и хочет, чтобы её опасность была как можно меньше.

Твоя задача — понять, как разложить детали по парам, чтобы максимальное произведение в паре было минимальным, и вывести это минимально возможное значение.

Важно: произведения могут не помещаться в 32-битный тип, ориентируйся на 64-битные целые (в Python это не проблема).

Формат ввода

• В первой строке дано чётное целое число N — количество деталей.
• Во второй строке дано N целых чисел a1, a2, …, aN — размеры деталей.

Формат вывода Выведи одно целое число — минимально возможное значение максимального произведения среди всех пар.

Ограничения

• 2 ≤ N ≤ 8000, N чётное
• 1 ≤ ai ≤ 10^9
• Время: 1 секунда, память: 256 МБ

Пример Ввод:

4
1 2 3 4

Вывод:

6

Ключевое наблюдение: нас волнует не сумма и не все произведения, а только самое большое произведение среди пар. Чтобы «приглушить» этот максимум, большие числа нельзя «встречать» друг с другом — иначе одна коробка станет слишком опасной.

Почему работает жадность: после сортировки пусть a[0] <= ... <= a[n-1]. Самый большой элемент a[n-1] в любом разбиении должен быть с кем-то в паре. Если дать ему не самый маленький, а более крупный элемент, произведение только вырастет. Значит, оптимально спарить a[n-1] с a[0]. Тот же аргумент повторяется для оставшихся элементов (обменный аргумент: любую пару с a[n-1] можно «улучшить», заменив партнёра на меньшего, не увеличив максимум).

План решения:

• Считай N и массив.
• Отсортируй массив.
• Поставь два указателя: i = 0 (минимум) и j = n-1 (максимум).
• Пока i < j:
• посчитай опасность пары p = a[i] * a[j];
• обнови ответ как ans = max(ans, p);
• сдвинь i += 1, j -= 1.
• Выведи ans.

Сложность: сортировка O(N log N), проход двумя указателями O(N), память O(1) сверх массива.

Частая ошибка: пытаться соединять соседние после сортировки (малые с малыми, большие с большими) — это обычно увеличивает максимум. В языках с фиксированными целыми не забудь 64-битный тип для произведения.