Наибольшее произведение

Даны $n$ целых чисел. Выберите три из них (на разных позициях) так, чтобы их произведение было максимальным.

В первой строке $n$ ($3 \le n \le 10^5$). Во второй — $n$ целых чисел ($|a_i| \le 10^6$).

Одно число — наибольшее произведение трёх чисел.

Отсортируйте массив. Ответ — большее из двух: произведение трёх наибольших чисел или произведение двух наименьших (они могут быть отрицательными) и наибольшего. Во втором примере все числа отрицательные: $(-5) \cdot (-12) \cdot (-30) = -1800$.

Произведение достигает $10^{18}$ — нужен 64-битный тип.

Источник: acmp.ru, задача 224.