Minimizing Remaining Milk Production

Farmer John’s arch‐nemesis, Farmer Paul, is planning to sabotage John’s milking machines! The machines are arranged in a row of N (3 ≤ N ≤ 100,000) units, where the ith machine produces M_i units of milk (1 ≤ M_i ≤ 10,000). Farmer Paul will disconnect a contiguous block of machines from the ith to the jth machine (with 2 ≤ i ≤ j ≤ N−1). Note that he never disconnects the first or last machine so as not to be too obvious. Even if it might be better not to sabotage, he will remove at least one machine.

After the disconnection, the remaining milk production average becomes \[ A = \frac{T - S}{N - L}, \] where T is the total milk production of all machines, S is the sum of milk produced by the removed block, and L is the number of machines removed. Farmer Paul wants to minimize A and Farmer John wants to know the worst‐case (minimum) average milk production if sabotage succeeds.

Your task is to compute the minimum average milk production of the remaining machines after Farmer Paul removes a contiguous block (with the restrictions above).

inputFormat

The input consists of two lines. The first line contains an integer N representing the total number of milking machines. The second line contains N space-separated integers, where the ith integer is M_i, the milk production of the ith machine.

outputFormat

Output the minimum possible average milk production of the remaining machines. Print the answer as a floating‐point number rounded to 6 decimal places.

sample

5
4 10 2 8 6

5.000000