Radio telescope
Problem
The radio telescope is trying to receive and analyze signals from space. Various noises are translated into a sequence of a real non-negative number, specified with an accuracy of 1 digit after the decimal point. In order to describe different parts of space, it was decided to characterize the data received from one region by a number equal to the maximum product that can be obtained by multiplying the values of the signals coming from this region. That is, it is required to choose such a non-empty subset of signals (it can include both one signal and all received signals), the product of values of which will be maximum. If there are several such subsets, then you can choose any of them.
Write an efficient program, including in terms of memory used, that will process the results of the experiment, finding the required subset. There can be a lot of signals, but it cannot be less than three. All signals are different.
Before the text of the program, briefly describe the algorithm you use to solve the problem.
Input
The number of signals N is given as input to the program in the first line. Each of the following N lines contains one real number with an accuracy of 1 digit after the decimal point. All numbers are different.
Imprint
The program should display in ascending order the numbers of signals, the product of which will characterize the given series. Signals are numbered starting from one.
Examples
| # |
Input |
Output |
| 1 |
5
12.3
0.1
100.2
0.3
1.4 |
1 3 5 |