Sabotage

Time limit1sMemory limit128 MB

Summary

Remove a contiguous block of middle machines, keeping the first and last, so the average output of the machines left is as small as possible.

Level: Medium6 of 10
Topics: Binary search, Prefix sum
Solved: No attempts yet

Problem

Farmer Paul's plan is to disconnect a contiguous block of milking machines, but not the first or the last one.

There are $N$ machines in a row. Machine $i$ produces $M_i$ units of milk ( $3 \le N \le 100\,000$ , $1 \le M_i \le 10\,000$ ). Paul may remove machines $i$ through $j$ with $2 \le i \le j \le N-1$ . He must remove at least one machine. After removal, what is the minimum possible average production of the machines that remain?

Farmer John wants that minimum average if Paul's plot succeeds.

Input

Line 1 contains the integer $N$ .

The next $N$ lines each contain $M_i$ for machine $i$ .

Output

Print the minimum achievable average, rounded to three digits after the decimal point, with exactly three digits after the decimal point.

Examples1

Example 1
Input
```
5
5
1
7
8
2
```
Expected output
```
2.667
```