Geometric Sequence

A sequence of integers is called a geometric sequence if the ratio of consecutive numbers is constant.
For example, (3,6,12,24) is a geometric sequence (each term is equal to twice the previous number)

Now, with such a sequence, we will shuffle it around and remove some of the elements.
Given the result of such a transformation, try to recover the "geometric ratio" of the original sequence.

If there are multiple values, output the one with the greatest absolute value (if there's still a tie, output the positive one)
If there is no such sequence, output 0.

Input

The number of integers, 2 ≤ N ≤ 100,000
N lines, each with one non-zero integer x ( |x| ≤ 10^18 )

Output

The ratio of the original sequence (if one exists).
The relative error of the answer must be within 10^-9. ( |answer - expected| / |expected| < 10^-9 )

Sample Input

3
1 3 27

Sample Output

3

The original sequence could have been 1,3,9,27 or 27,9,3,1; the former has the greater ratio.

All Submissions
Best Solutions


Point Value: 10
Time Limit: 1.00s
Memory Limit: 64M
Added: Sep 26, 2008
Author: hansonw1

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

If I have a partial geometric sequence (a geometric sequence with numbers possibly removed), the ratios between adjacent numbers will form another partial geometric sequence with the same ratio as the original (if arranged properly)

hint: sort them

N seems to be really big, but does it matter?

hint: cause if n is too large, the numbers in the sequence will be too large, so n should be around 100

didn't see that there is possibly no such sequence......
that makes my algorithm totally fail = =
gonna take a break XD


A non-integer ratio, you mean? Of course. It would be too easy otherwise.
Note:
The relative error of the answer must be within 10^-9. ( |answer - expected| / |expected| < 10^-9 )

If the answer were guaranteed to be an integer, this line would be unnecessary, since integers are exact numbers. These lines are only included when the answer can be a floating-point number, because then your answer might be off by a tiny bit depending on how you obtained it - meaning it will still be judged correct if you have an error of less than one part in a billion (thousand million?)

Use long doubles; they can store more than 18 digits.