Given N numbers in a circle, we can determine a continuous subsequence by giving its start position and its length. PMH and Roy played a game the other day. Roy gives the start position first, then PMH gives the length. Roy wants the mean of the subsequece as large as possible, but he doesn't know the length that PMH will choose. Assume that the length L(0 < L <= N) PMH will choose is random, so there are N possible means that Roy may get. For each start position, there is a mean of all the N means described above, and Roy will choose the start position with the maximal mean.
Input
There are multiple test cases.
Each test case begins with a line containing N only (N < 20000 and N is power of 2).
The following line contains N numbers, separated by spaces.
Output
For each test case, you are to print the maximal mean Roy can get, accurate up to 2 decimal places.
Sample Input
4
1 2 3 4
Sample Output
2.92
Note
Assume the start position is 1.
If PMH chooses the length 1, the mean of the subsequece is 1 / 1 = 1.
If PMH chooses the length 2, the mean of the subsequece is (1 + 2) / 2 = 1.5.
If PMH chooses the length 3, the mean of the subsequece is (1 + 2 + 3) / 3 = 2.
If PMH chooses the length 4, the mean of the subsequece is (1 + 2 + 3 + 4) / 4 = 2.5.
So we get the mean of 1, 1.5, 2 and 2.5 as 1.75.
If Roy let the start position be 3, he can get the maximal mean 2.92.
