Searching for Extraterrestrial Intelligence

The representation of a signal in the frequency domain is its spectrum. It is extremely important to observe that artificial signals (signals produced by artificially constructed systems) have a unique characteristic spectrum distribution. This distribution is also called a characteristic triplet because two signals of the same power, both smaller than ~50~% of the power corresponding to the characteristic frequency, appear symmetrically and on either side of a given frequency.

The University of Berkeley (California, U.S.A.) has developed an international program for signal processing using volunteers from the Internet, aiming to search for extraterrestrial intelligence based on the analysis of signals collected by radio telescopes (http://setiathome.berkeley.edu/ ). Berkeley collects signals from radio telescopes and, after initial processing, distributes them to participants in the program for further processing. What is requested in this problem is a simplified version of the processing that participants are asked to perform.

Transformation of a signal from the time domain to the frequency domain.

Problem:

Develop a program in one of the IOI languages that reads values corresponding to a signal and recognizes the characteristic frequencies.

A triplet in a signal is a set of three values of the signal with the following properties: (a) the two extreme values are equidistant from the median, and (b) the two extreme values are equal to each other and less than half of the median value. For example, the triplet of values shown in bold below is a triplet:

The median value of a triplet gives us the characteristic frequency, which is equal to the position of the median value in the signal. In the example above, the characteristic frequency is ~6~ (because the median value ~5~ is the sixth number appearing in the signal).

Input Files

The input files with the name seti.in are text files with the following structure: They consist of exactly two lines. The first line contains an integer ~N\;(10 \le N \le 10.000)~, which corresponds to the number of values in the signal we have recorded. The second line contains ~N~ integers separated in pairs by spaces.

Output Files:

The output files with the name seti.out are text files with the following structure: The first line contains an integer ~K\;(0 \le K \le N)~. This number expresses the count of characteristic frequencies detected. Then follow ~K~ lines, each of which has an integer ~M\;(2 \le M \le N - 1)~. The number ~M~ represents a characteristic frequency, i.e., the position of the median value of the corresponding triplet within the signal (counting starts from ~1~). The characteristic frequencies should be given in ascending order. If multiple triplets correspond to a characteristic frequency, the frequency should be listed only once.

Examples of Input - Output Files:

1st

STDIN (seti.in)

20
1 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

STDOUT (seti.out)

1
3

Explanation: There is only one triplet.
1 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

2nd

STDIN (seti.in)

25
4 4 5 5 5 6 6 6 6 7 7 7 6 6 6 6 5 5 5 4 4 3 2 1 0

STDOUT (seti.out)

0

Explanation: There is no triplet.

3d

STDIN (seti.in)

12
1 2 2 5 3 2 1 6 1 2 1 4

STDOUT (seti.out)

3
4
5
8

Explanation: There are three characteristic frequencies.
1 2 2 5 3 2 1 6 1 2 1 4 και 1 2 2 5 3 2 1 6 1 2 1 4
1 2 2 5 3 2 1 6 1 2 1 4
1 2 2 5 3 2 1 6 1 2 1 4 και 1 2 2 5 3 2 1 6 1 2 1 4

Maximum Time: 2 sec