Subsequence Problem

You must be very familiar with the classic maximum subsequence problem:

Given an integer sequence A₁, A₂, ..., A_n, Find a continuous subsequence A_[i..j] with maximum sum: A_i + A_i+1 + ... + A_j. (1 <= i <= j <= n)

As a talented ACMer, you can solve this problem in seconds. So here comes a harder version:

Given an integer sequence A₁, A₂, ..., A_n, Find a continuous subsequence A_[i..j] with maximum average value: (A_i + A_i+1 + ... + A_j) / (j - i + 1). (1 <= i <= j <= n)

As a talented ACMer, you can solve this problem in minutes. So here comes a more harder version:

Given an integer sequence A₁, A₂, ..., A_n, Find a continuous subsequence A_[i..j] with maximum squared average value: (A_i + A_i+1 + ... + A_j)^2 / (j - i + 1). (1 <= i <= j <= n)

As a talented ACMer, can you solve this problem?

The first line of each test case contains one integer n (1 <= n <= 100,000), the length of the original sequence. The next line contains n integers A₁, A₂, ..., A_n. (-1,000 <= A_i <= 1,000)

Output one real number for each test case, indicating the max squared average value described above. You will get accepted if the difference between your answer and standard answer is no more than 10-4.

3
1 5 4
3
3 5 4

40.500000
48.000000

TJU

2012 Multi-University Training Contest 2