Наибольшее произведение трех чисел
Задача
В данном списке из N≤106 целых чисел найдите три числа, произведение которых максимально.
Решение должно иметь сложность O(N), где N - размер списка.
Выведите три искомых числа в порядке невозрастания.
Входные данные
В первой строке задано целое число 3 ≤ N ≤ 100 000 — количество элементов в списке.
Во второй строке заданы N целых элементов списка, не превосходящих по модулю 30000.
Выходные данные
Ответ на задачу.
Примеры
| входные данные |
выходные данные |
|
9
3 5 1 7 9 0 9 -3 10
|
10 9 9
|
|
3
-5 -30000 -12
|
-5 -12 -30000
|
Запрещенные операторы: max; min; count; sort