Радиотелескоп пытается получать и анализировать сигналы из космоса. Различные шумы переводятся в последовательность вещественного неотрицательного числа, заданного с точностью до 1 знака после десятичной точки. Для того, чтобы описывать различные участки космоса, данные, получаемые из одного района, было решено характеризовать числом, равным максимальному произведению, которое можно получить, перемножая значения сигналов, приходящих из этого района. То есть требуется выбрать такое непустое подмножество сигналов (в него может войти как один сигнал, так и все поступившие сигналы), произведение значений у которого будет максимальным. Если таких подмножеств несколько, то выбрать можно любое из них.
Напишите эффективную, в том числе по используемой памяти, программу, которая будет обрабатывать результаты эксперимента, находя искомое подмножество. Сигналов может быть очень много, но не может быть меньше трех. Все сигналы различны.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
Входные данные
На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно вещественное число с точностью до 1 знака после десятичной точки. Все числа различны.
Выходные данные
Программа должна вывести в порядке возрастания номера сигналов, произведение которых будет характеризовать данную серию. Нумерация сигналов ведется с единицы.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
12.3
0.1
100.2
0.3
1.4 |
1 3 5 |